“Perket” 是一种家喻户晓的美食。为了制作出正宗的 Perket，厨师们必须仔细选择配料，以在保持传统风味的同时获得最丰富的口感。

你有 $N$ 种配料可供使用。对于每种配料，我们知道它的酸度 $S$ 和苦度 $B$。当使用多种配料时，总酸度是所有配料酸度的乘积，而总苦度是所有配料苦度的总和。

众所周知，Perket 既不应该太酸，也不应该太苦；我们希望选择配料，使得总酸度和总苦度之间的绝对差最小。

此外，必须至少使用一种配料；你不能把白开水当作主菜端上桌。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10$)，表示可用的配料数量。

接下来的 $N$ 行，每行包含两个用空格隔开的整数，分别表示每种配料的酸度和苦度。

输入数据保证，如果用所有的配料制作一道菜，其总酸度和总苦度都将小于 $1\,000\,000\,000$。

输出格式

输出总酸度和总苦度之间可能的最小绝对差。

样例

输入样例 1

1
3 10

输出样例 1

7

输入样例 2

2
3 8
5 8

输出样例 2

1

输入样例 3

4
1 7
2 6
3 8
4 9

输出样例 3

1

说明

在第三个样例中，我们选择最后三种配料。总酸度为 $2 \times 3 \times 4 = 24$，总苦度为 $6 + 8 + 9 = 23$。它们的差值为 $1$。