### 2008 Canadian Computing Competition, Day 2

## Day 2, Problem 2: Candy

You and a friend have a big bag of candy. You want to keep slim and trim, and so you would like to equalize the candy which you are sharing with your friend in terms of calorie count. That is, your task is to divide the candies into two groups such that the number of calories in each group is as close together as possible.

### Input

The first line of input contains the number of different kinds of candy you have in your
bag of candy N (1 ≤ N ≤ 100). On the following N lines, there are pairs of numbers
describing each type of candy. The candy description is of the form k_{i} c_{i} where k_{i} is the
number of that particular type of candy contained in the bag and c_{i} is the calorie count for
each piece of that type of candy. You may assume that 1 ≤ k_{i} ≤ 500 and 1 ≤ c_{i} ≤ 200.

### Output

Your output is one integer which is the minimum difference of calories between friends

### Sample Input

4 3 5 3 3 1 2 3 100

### Sample Output

74

### Explanation

Your friend takes two of the 100-calorie candies, for a total of 200 calories. You keep the remaining candies, which have 126 calories.

### Grading

You may assume that 50% of the test cases will have at 1 ≤ N, k_{i}, c_{i} ≤ 100. All test
cases will have 1 ≤ N ≤ 100, 1 ≤ k_{i} ≤ 500 and 1 ≤ c_{i} ≤ 200. You solution must use at most
512MB of memory and run in at most 6 seconds.

All Submissions

Best Solutions

**Point Value:** 20

**Time Limit:** 6.00s

**Memory Limit:** 512M

**Added:** Dec 07, 2008

**Languages Allowed:**

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

## Comments (Search)

bleung91on Dec 30, 2008 - 9:47:26 pm UTC assignment and not using expressions in for loopsbbi5291on Dec 31, 2008 - 3:46:59 pm UTC Re: assignment and not using expressions in for loopswith

?

Obviously the first is slower than the second, but usually this isn't the difference between AC and TLE...