Candy

Interview

Time limit1sMemory limit128 MB

Summary

Split multiset candies with counts and calorie values into two groups so the two calorie totals differ as little as possible.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Greedy, Math
Solved: No attempts yet

Problem

You and a friend share a big bag of candy, and you both want to stay slim. To be fair, you want to split all of the candy into two groups so that the two groups are as equal as possible in total calories.

The bag holds $N$ kinds of candy. For kind $i$ you have $k_i$ identical pieces, and every piece of that kind has $c_i$ calories. You assign each individual piece to one of the two groups (pieces of the same kind may be placed in different groups). Find the smallest possible difference between the total calories of the two groups.

Input

The first line contains the number of kinds of candy $N$ ( $1 \le N \le 100$ ).

Each of the next $N$ lines contains two integers $k_i$ and $c_i$ : the number of pieces of that kind ( $1 \le k_i \le 500$ ) and the calories of each such piece ( $1 \le c_i \le 200$ ).

Output

Print one integer: the minimum possible difference in total calories between the two groups.

Hint

In the sample, one group takes the two $100$ -calorie candies (total $200$ ) and the other group keeps the remaining candies (total $126$ ). The difference is $200 - 126 = 74$ , which is the smallest achievable.

Examples4

Example 1
Input
```
4
3 5
3 3
1 2
3 100
```
Expected output
```
74
```
Example 2
Input
```
1
1 1
```
Expected output
```
1
```
Example 3
Input
```
1
2 5
```
Expected output
```
0
```
Example 4
Input
```
2
1 1
1 2
```
Expected output
```
1
```