Al's been put in charge of an important government job. His boss Mike told him to shuffle provincial and municipal responsibilities around so that as much spending responsibility changes hands as possible, but also so that the net spending change for either party is zero.
Al's not too good with numbers, so you're going to write a program to help him out.
Input: A sequence of lines. Each line is an alphabetic string describing a government responsibility, followed by one or more spaces, followed by a positive decimal integer representing the number of millions of dollars spent fulfilling that responsibility. Descriptions of municipal responsibilities have an upper case first letter; descriptions of provincial responsibilities have a lower case first letter.
Output: The output is a single number. It represents the maximum amount of spending responsibility that can be exchanged between provincial and municipal levels, without making either level spend any more (or less).
The answer will always be less than 10000.
Sample (made up!) input:
StreetCleaning 10 ParksUpkeep 30 Education 1400 Sewers 75 Fire 100 roads 500 provincialPolice 120 legislature 10 provincialElections 5 hospitalMaintenance 100 subsidizedHousing 400Corresponding sample output:
130