Time Limits: 1000 ms Memory Limits: 65536 KB

Description

佳肴就是非常美味的菜的意思，佳肴最关键的是选择好原料。
　　现在有N种原料，每种原料都有酸度S和苦度B两个属性，当选择多种原料时，总酸度为每种原料的酸度之积，总苦度为每种原料的苦度之和。
　　正如大家所知，佳肴是既不酸也不苦的，因为要保证所选的原料使得总酸度和总苦度差的绝对值最小。
　　由于佳肴不能只有水，所以必须至少选择一种佳肴。

Input

输入第一行包含一个整数N（1<=N<=10），表示原料的种数。
　　接下来N行每行包含两个用一个空格隔开的整数，分别表示酸度和苦度。
　　输入数据保证如果所有原料都选上，总酸度和总苦度不会超过10^9。

Output

输出总酸度和总苦度最小的差。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入1：
1
3 10

输入2：
2
3 8
5 8

输入3：
4
1 7
2 6
3 8
4 9

Sample Output

1
2
3
4
5
6
7
8
输出1：
7

输出2：
1

输出3：
1

Data Constraint

Hint

【样例解释】
　　样例3中选择最后三种原料，这样总酸度为2×3×4=24，总苦度为6+8+9=23，差为1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
int x[11],y[11],b[11];
int n,ans=1<<31-1;
void dfs(int u,int v)
{
    ans=abs(u-v)<ans?abs(u-v):ans;
    for (int j=1;j<=n;j++)
        if (!b[j])
        {
            b[j]=1;
            dfs(u*x[j],v+y[j]);
            b[j]=0;
        }
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    for (int i=1;i<=n;i++)
    {
        b[i]=1;
        dfs(x[i],y[i]);
        b[i]=0;
    }
    cout<<ans;
}