PGA Tour Prize Money

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 A PGA (Professional Golf Association) Tour event is a golf tournament in which prize money is awarded to the best players. The tournament is broken into four rounds of 18 holes apiece. All players are eligible to play the first two rounds. Only those with the best scores from those 36 holes ``make the first cut" to play the final two rounds and qualify for prize money. Players with the best 72-hole aggregate scores (the lowest scores) earn prize money.

 

You must write a program to determine how the total prize money (called the tournament ``purse") is to be allocated for a tournament. Specifications are as follows.

 

1)
All players will play at least two 18-hole rounds (36 holes in all) unless they are disqualified for some reason.
2)
Any player who is disqualified stops playing at the time of the disqualification. Players who are disqualified during the first two rounds are ineligible to make the cut. Players who are disqualified during either of the last two rounds are ineligible to win prize money.
3)
At the end of the first two rounds, the field of players is cut to the 70 players with the lowest 36-hole scores plus ties. So if 10 players are tied for 70th place, then 79 players make the 36-hole cut. Players who do not make the 36-hole cut are eliminated from the playing field and do not win any prize money.
4)
The players who do make the 36-hole cut play an additional 36 holes (two 18-hole rounds) and are paid a percentage of the total prize money depending on their 72-hole aggregate score. The lower the score, the more prize money a player wins.
5)
Players are paid percentages of the the tournament purse according to their final standings. For example, if the tournament purse were $1,000,000 and the winner's share were 18%, the winner would earn $180,000.
6)
There will be only one winner of this tournament. (In an actual golf tournament, when there is a tie for the low 72-hole score, there is be a play-off among the tied players. We will ignore that situation.)
7)
There may be a tie for any or all of the positions between 2 and 70. If there is a tie among n players for position k, the money designated for positions k through n + k - 1 is pooled and allocated equally among the tied players. For example, using the sample data given later, if there were a tie for second place between two golfers, they would each win $88,000 [(10.8% + 6.8%)/2 = 8.8% * $1,000,000]. If there were a three-way tie, all three golfers would get $74,666.66 [(10.8% + 6.8% + 4.8%)/3 = 7.4666% * $1,000,000]. The extra penny is ignored.
8)
If disqualification reduces the field to less than 70 players, the money for the last and any other places not covered is not allocated. For example, if exactly 70 players make the cut but three of them are disqualified, then the tournament simply pays 67 places.
9)
Amateur golfers may play in professional tournaments but can win no money. Any prize money ``won" by an amateur is allocated to the next lower position. For example, if an amateur has placed third in a tournament, then third place money goes to the fourth place finisher, and fourth place money goes to the fifth place finisher, etc.
10)
Only the low 70 non-amateur places and ties earn prize money. For example, if 75 players make the 36-hole cut, it is possible for 5 of them not to earn prize money, assuming none of the players making the cut are amateurs. 

Input

The input contains multiple tournaments. There's line with number of players attending the tournament (always less than 145) and then follow two segments of data of the tournament. Zero players denotes end of input file. The amount of the tournament purse and the percentages for all the 70 places are stored in the first segment of the input file. This segment contains exactly 71 lines, which are formatted as follows.

 

   Line 1: 	 Total value of the purse  Line 2: 	 Percentage of the purse designated for first place  Line 3: 	 Percentage of the purse designated for second place  ...  Line71: 	 Percentage of the purse designated for 70th place 

The purse is given to two decimal places. All percentages are given to four decimal places. Assume the percentages are correct and sum to 100%. No tournament has purse bigger than $40 millions. A partial sample of the first segment of the input file is shown below.

 

1000000.00
18.0000
10.8000
6.8000
4.8000
...
0.2020
0.2000

The second segment contains the players' names and their respective scores for the four rounds. The format of each line is as follows.

 

   Characters 1-20:  Player name  Character  21:    Single space        Characters 22-24: Round 1 score (first 18 holes)  Character  25:    Single space  Characters 26-28: Round 2 score (second 18 holes)  Character  29:    Single space  Characters 30-32: Round 3 score (third 18 holes)  Character  33:    Single space  Characters 34-36: Round 4 score (fourth 18 holes) 

Any player who has an asterisk `*' as the last non-space character in name column is an amateur. All players who are not disqualified will have four 18-hole scores listed. (Even though in an actual tournament, players who do not make the cut do not get to play the last two rounds of the tournament, for the purposes of this program all players who are not disqualified will have four 18-hole scores listed.) A player who is disqualified during a round will have a score on that round shown as `DQ'. That player will have no additional scores for the tournament. Assume that at least 70 players will make the 36-hole cut.

 

Sample lines from the second segment of the input file are as follows.

 

WALLY WEDGE          70  70  70  70
SANDY LIE            80  DQ
SID SHANKER*         100 99  62  61
JIMMY ABLE           69  73  80  DQ

Output

 Output from this program consists of names of all players who made the 36-hole cut, their finish positions (with the letter ``T" after the numeric value representing the finish position if there is a tie for that position , write the players with tie in the order they were in input set ), scores for each round, total scores, and the amounts of money won. Disqualified players are listed at the bottom with scores of DQ placed in the ``TOTAL" column; those disqualified should be written in the order they appeared in input set. No player who failed to make the 36-hole cut is listed in the output. Each column of output should be formatted and labelled appropriately. The dollar amounts should be correct to two decimal places. Note that Money Won column is right aligned, and that amateure golfers as well as disqualified ones have that column filled with spaces until the right edge of table. At the end of table write empty line to separate distinct tournaments. Sample output is shown below: Note: The ruler is written here only for your convenience, don't write it in output of your program.

 

         1         2         3         4         5         6
12345678901234567890123456789012345678901234567890123456789012345
Player Name          Place RD1  RD2  RD3  RD4  TOTAL    Money Won
-----------------------------------------------------------------
WALLY WEDGE          1     70   70   70   70   280      180000.00
TOMMY TWO IRON       2T    71   72   72   72   287       88000.00
HENRY HACKER         2T    77   70   70   70   287       88000.00
NORMAN NIBLICK*      4T    72   72   72   72   288               
BEN BIRDIE           4T    70   74   72   72   288       48000.00
...
LEE THREE WINES      70    99   99   99   99   396        2000.00
JIMMY ABLE                 69   73   80        DQ                
EDDIE EAGLE                71   71             DQ                

Sample Input


				

Sample Output


				

Hint


Source