## CCO '08 P5 - Candy

View as PDF

Points: 7 (partial)
Time limit: 2.75s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Canadian Computing Competition: 2008 Stage 2, Day 2, Problem 2

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 Specification

The first line of input contains the number of different kinds of candy you have in your bag of candy . On the following lines, there are pairs of numbers describing each type of candy. The candy description is of the form where is the number of that particular type of candy contained in the bag and is the calorie count for each piece of that type of candy. You may assume that and .

#### Output Specification

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 for Sample Output

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