DWITE, December 2011, Problem 1

This non-discriminatory year-end holiday season you have received a present. It has to stay neatly wrapped for some time, but you want to know what it is now. Estimating the weight of the package, and the weights of possible presents, pick the closest match.

The input will contain 5 test cases, each 5 lines long. The first line will be an integer value, the weight of the package. The following 4 lines will contain possible choices, each in the form: name weight, where name is a single word and weight is an integer weight for this choice.

The output will contain 5 lines of output, each name of the closest guess out of the choices. If two items tie, then answer with the heavier of the two.

Sample Input

-2
helium -3
air 0
socks 1
brick 10
4
brick 10
books 7
socks 1
air 0

Sample Output

helium
books

Problem Resource: DWITE