题目描述

Perket 是一种流行的美食。

现在有 $n$ 种可供选择的食材。对于第 $i$ 种食材，已知它的酸度为 $s_i$，苦度为 $b_i$。

如果选择若干种食材制作 Perket，则：

• 总酸度等于所有被选食材酸度的乘积；
• 总苦度等于所有被选食材苦度的总和。

为了让味道尽可能均衡，希望选择一些食材，使总酸度与总苦度的绝对差尽可能小。

至少需要选择一种食材。

请你计算总酸度与总苦度的最小绝对差。

输入格式

第一行输入一个整数 $n$，表示可供选择的食材种类数。

接下来 $n$ 行，每行输入两个整数 $s_i$ 和 $b_i$，分别表示第 $i$ 种食材的酸度和苦度。

输出格式

输出一个整数，表示所有非空食材选择方案中，总酸度与总苦度的最小绝对差。

样例

1
3 10

7

2
3 8
5 8

1

4
1 7
2 6
3 8
4 9

1

样例解释

样例 $3$ 中，可以选择最后三种食材。

此时总酸度为：

总苦度为：

二者的绝对差为：

因此答案为 $1$。

数据范围

$1 \le n \le 10$。

保证将所有可用食材全部使用时，产生的总酸度和总苦度均小于 $10^9$。

来源：洛谷P2036