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 ki ci where ki 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 ≤ ki ≤ 500 and 1 ≤ ci ≤ 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: 2020-02-05 11:36:53

Nice dp problem

You have to optimize this problem with 1 dimension state ...
..learnt something new

cegprakash: 2019-05-06 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: 2019-05-07 18:19:46
mahmud2690: 2017-03-01 15:51:38

One of obvious optimization is to notice maximum value of the result.

weiwei zhong: 2014-08-12 01:34:26

Hi! may I have a hint to which I can improve my program's algorithm? ^^" thanksss

Dummer Pedraza: 2011-11-19 13:39:57

tiempo 2 sec pero WA

Aamir Khan: 2011-10-06 17:22:04

What is the expected complexity to solve this problem ? I am getting TLE..

anonymous: 2010-03-29 13:35:30

please include this case in the test data
it will fail some of the passed solutions

2
197 5
5 197

JaceTheMindSculptor: 2009-08-22 01:13:48

Let me state clearly:

O(N*S) algorithms will not be sufficient to pass the time limit.

Drew Saltarelli: 2009-08-21 17:56:33

wow, strict time limit :(

JaceTheMindSculptor: 2009-06-21 04:44:32

◄ ►: There is a simple optimization which will allow your code to pass.


Added by:JaceTheMindSculptor
Date:2009-04-08
Time limit:1s-2.397s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Canadian Computing Competition 2008 Stage 2 Question E