COCI 2008/2009, Contest #2

Task PERKET

"Perket" is a widely known and delicious meal. For perket to be what it is, cooks must carefully choose the ingredients to get the fullest taste possible while keeping the meal traditional.

You have N ingredients at your disposal. For each we know its sourness S and bitterness B. When using multiple ingredients, the total sourness is the product of sourness amounts of all ingredients, while the total bitterness is the sum of bitterness amounts of all ingredients.

As everyone knows, perket is supposed to be neither sour nor bitter; we want to choose the ingredients so that the absolute difference between sourness and bitterness is the smallest.

Also, it is necessary to use at least one ingredient; you can't serve water as the main course.

Input

The first line contains the integer N (1 ≤ N ≤ 10), the number of ingredients at our disposal.

Each of the next N lines contains two integers separated by a space, the sourness and bitterness of each ingredient.

The input data will be such that, if we make a meal with all ingredients, both the sourness and bitterness will be less than 1,000,000,000.

Output

Examples

1
3 10

7

2
3 8
5 8

1

4
1 7
2 6
3 8
4 9

1

In the third example, we choose the last three ingredients. The total sourness is then 2x3x4=24 and bitterness is 6+8+9=23. The difference is 1.

All Submissions
Best Solutions

Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 21, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Why in the third example we only chose the last three? I don't get it.

you pick the combination of ingredients that gives you the minimum difference.

to fidn the total sourness, you multiply all ingredients and total bitterness, you add all ingredients.

so if I have 10 ingredients, I could use all 10, or I could only use 1.  get it?

Can someone tell me what the problem is? My program definitely compiles on my computer and I have no idea why it doesn't here

Which compile error is it?

It is very long, i don't really understand but here it is
: In function 'void core(int, int, int)':
:15: error: reference to 'min' is ambiguous
:5: error: candidates are: long int min
/usr/include/c++/4.1.3/bits/stl_algobase.h:228: error: template const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
/usr/include/c++/4.1.3/bits/stl_algobase.h:184: error: template const _Tp& std::min(const _Tp&, const _Tp&)

and it keeps repeating that over and over again.

On my computer the program runs and works properly, at least for small test cases 

[i]min[/i] is a function, so you can't call a variable the same thing.
(Sometimes it works, and sometimes it doesn't - I don't know why)

It works on Visual C++ 6.0 because min is not defined there.