2000 ACM South Central Regional Programming Contest

Louisiana State University

Problem #3: Election

Introduction

After numerous recounts of the presidential votes in Florida, candidates George W. Bush (Republican) and Al Gore (Democrat) are unconvinced of the accuracy of the results. Each candidate is convinced that he should receive Florida's electoral votes needed to win the presidency and no amount of recounting the ballots will determine a clear winner. Also, it was revealed that some of the volunteers forgot to turn in several ballot boxes, and are currently unavailable on vacation at Disney World.

The U.S. population is justly demanding a resolution to the problem to avoid a third term under Clinton. Political analysts insist that they can determine which candidate the state will be awarded to, based on the income levels of its districts' residents. Jeb Bush, the governor of Florida, has asked you to write a program that will determine which candidate will win Florida, and ultimately the election. The future of the country rests in your hands.

The program will be based on the electoral college system, extended to the district level. Each district is worth a certain number of electoral votes, with the winner of the district determined by the median income of its residents. Exit polls have revealed that if the median income of the district is greater than a certain level, it will be awarded to the Republican candidate. A simple majority of electoral votes is needed to win the entire state (a tie will result in the deciding vote being cast by Jeb, resulting in a Republican victory).

Input

Input will consist of a non-zero number of independent data sets containing election information. Each election data set will conform to the following:

  1. The first line of a data set will be 'START'.
  2. The next two lines (this is a run-off election, no third-party candidates) will contain the names of the Democratic candidate coming first.
  3. The fourth line will contain the number of districts.
  4. The fifth line will contain the target median income level. A district with a median income greater than the target will have its electoral votes go to the Republican candidate. All other electoral votes will go to the Democratic candidate.
  5. Each of the next lines will contain a district's name, its median income level (formatted as a simple integer), and its number of electoral votes (also an integer), each separated by a comma.
  6. The last line of a data set will be 'END'.

There will be no blank lines in the input, but there will be an endline just before the end of the input.

Output

The output will be the results of the elections from the input. For a given election set, the output will consist of a line containg the winning candidates' name and his number of electoral votes, separated by a comma (there will be no spaces on either side of the comma):

George W. Bush,96

There will be no blank lines separating output sets.

Sample Input

START
Al Gore
George W. Bush
12
39000
North,50000,10
Northnortheast,30000,18
Northeast,40000,11
East,40000,15
Southeast,43000,13
Southsoutheast,52000,14
South,47000,9
Southsouthwest,25000,20
Southwest,25000,24
West,60000,12
Northwest,39000,11
Northnorthwest,35000,12
END
START
Bleed N. Hart
Pub Lee Kahn
4
37000
North,25000,40
East,35000,20
South,40000,30
West,45000,20
END

Sample Output

Al Gore,85
Bleed N. Hart,60