시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 4 | 1 | 1 | 25.000% |
Every year, the continent of Cacophonea organises the Cacophonean Song Contest, for which each of its nations presents an act by a national singer or group. Each Cacophonean inhabitant may televote for any act which is not from his nation, so a nation can never vote for its own act. In the end, each of the s Cacophonean nations will award points to r acts. The act which received most votes from a certain nation will get r points from this nation, the act with the second largest amount of votes will get r − 1 points, etc., so the act with the rth largest amount of votes gets 1 point and less popular acts get no points from the voting nation. The final ranking of the song contest will then be decided by the total amount of points each nation received.
Music producer Dustin has been eagerly following the Cacophonean Song Contest for many years. Lately, he has observed that in certain nations, televotes are politically rather than artistically motivated:
However, Dustin has heard he can influence the voting behaviour of other nations: an artist can find favour of politically voting nations by giving them special attention during his act (e.g. by singing parts in their local dialects, waving their flags, etcetera). The more a politically voting nation will receive such attention in an act, the higher it will rank it. Of course this will be at the cost of the original act and might result in terribly campy results. Therefore, nations that vote according to artistic quality will punish such behaviour.
More specifically, Dustin can divide an act into exactly s − 1 parts. Originally, all parts are dedicated to the nation of the performer (i.e. they reflect his original artistic ideas), but this can be changed:
Only the fact that a certain amount of parts is dedicated to a certain nation will influence voting behaviour: the exact part dedication sequence in the total act is not of interest here.
Dustin wants to use this knowledge (which no other Cacophonean producer has) to produce a smashing act, yielding as much points in the overall results as possible. You are asked to determine what the largest possible overall point score is he can obtain for an act, when he optimally exploits the described act-changing practices.
For each test case, the output contains a single line with a single integer number: the maximal amount of points an act can obtain in the overall final score, if act-changing practices were performed in an optimal way.
2 3 Aulatrias q 0 0 1 Binen q 5 0 2 Cahin q 0 -4 3 2 Cahin 3 Aulatrias p 0 0 1 Binen p 5 0 2 Cahin p 0 -4 3 2 Binen
2 4