FCANDY  Candy (Again)
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 ci 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
Example
Input: 4 3 5 3 3 1 2 3 100 Output: 74
hide comments
scolar_fuad:
20200205 11:36:53
Nice dp problem


cegprakash:
20190506 23:39:34
I learnt something new. The strict time limit though let me make assumptions without proof and that helped me get an AC! Last edit: 20190507 18:19:46 

mahmud2690:
20170301 15:51:38
One of obvious optimization is to notice maximum value of the result. 

weiwei zhong:
20140812 01:34:26
Hi! may I have a hint to which I can improve my program's algorithm? ^^" thanksss 

Dummer Pedraza:
20111119 13:39:57
tiempo 2 sec pero WA 

Aamir Khan:
20111006 17:22:04
What is the expected complexity to solve this problem ? I am getting TLE.. 

sudipto das:
20100510 11:55:43
Last edit: 20120118 08:33:02 

anonymous:
20100329 13:35:30
please include this case in the test data


JaceTheMindSculptor:
20090822 01:13:48
Let me state clearly:


Drew Saltarelli:
20090821 17:56:33
wow, strict time limit :( 
Added by:  JaceTheMindSculptor 
Date:  20090408 
Time limit:  1s2.397s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  Canadian Computing Competition 2008 Stage 2 Question E 