You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

调味

题目描述

你是一个厨师，正在研究一道菜怎么做最好吃。你有 $n$ 种调味品，每种调味品分别有一个酸度 $s$ 和苦度 $b$。当你添加调味品时，总的酸度为每一种调味品的酸度总乘积；总的苦度为每一种调味品的苦度的总和。

众所周知，美食应该做到口感适中，所以顾客们希望最后做出来的菜里面，酸度和苦度的绝对差最小。

另外，你必须添加至少一种调味品，不然顾客只喝水是会投诉你的。

输入格式

第一行一个整数 $n$，表示可供选用的调味品种类数。

接下来 $n$ 行，每行 $2$ 个整数 $s_i$ 和 $b_i$，表示第 $i$ 种调味品的酸度和苦度。

输出格式

一行一个整数，表示可能的总酸度和总苦度的最小绝对差。

样例 #1

样例输入 #1

4
1 7
2 6
3 8
4 9

样例输出 #1

1

提示

数据范围

对于 $100\%$ 的数据，有 $1 \leq n \leq 17$，且将所有可用调味品全部使用产生的总酸度和总苦度小于 $10^{18}$，酸度和苦度不同时为 $1$ 和 $0$。