TopCoder

User's AC Ratio

94.1% (16/17)

Submission's AC Ratio

44.1% (26/59)

Description

職棒打假球事件重創了我國的職業棒球運動,
有許多球星因為涉案而遭球團開除退出職棒,這也使許多球隊面臨了球員不足的窘境。

因此在這段時間各球團都很積極地在自由球員市場物色適當的球員來補足戰來的缺口,
而且各球團的總經理都正為同一個問題煩惱,即如何在有限的經費下與適合的球員簽約,使球隊的戰力獲得最大的提昇。

更具體的來說,假設標哥是某職棒球隊的總經理,
他有M(≤ 10000)單位的預算可以用來與球員簽約,且他的球隊有 N 個位置需要引進球員補強,
為了簡化問題假設每個位置都有 P 位自由球員可供選擇,這 N 個位置可以是有關打擊、手備或投手等位置的補強,
每位自由球員只專注於一個位置,故總共會有NP 位自由球員可供考慮,每個位置最多只補一位自由球員,因為該位置可能已有球員負責。
此外每位球員有三項資訊可供標哥參考並決定是否與該球員簽約,即該球員(1)負責的位置、(2)簽約金額(<=10000)、(3)戰力指數(<=100)。
戰力指數是一非負整數用來衡量一球員的能力,戰力指數愈大表示能力愈強。

給定球隊的預算及須要補強的位置數以及所有相關球員的資訊,
你的任務是寫一個程式幫標哥計算如何在預算內簽下自由球員以補充戰力並且使所簽下的球員戰力指數總和最大。

Input Format

第一行輸入三個正整數 M(≤ 10000)、N(≤ 50)及 P(≤ 50)分別代表標哥的預算、所須補強的位置數以及每個位置的人選個數。
接下來的 N行中,每一行則輸入 2P 個正整數,
其中第 I 行用來代表可以勝任第 I 個位置的球員資訊,
兩個數字一組分別用來描述一位球員的簽約金及戰力指數,數字間以一或多個空白區隔。

Output Format

輸出一數字顯示標哥所能簽到的最大戰力指數總和。

Sample Input

Sample Input #1:

10000 2 3
5000 2 10000 5 5000 1
5000 6 10000 5 5000 5


Sample Input #2:

10000 3 3
1000 2 1000 3 10000 5
10000 3 5000 6 3000 5
1000 7 2000 5 2000 6


Sample Output

Sample Output #1:

8


Sample Output #2:

16

Hints

本題保證所有計算過程都不會超出32位元有號整數。

Problem Source

原TIOJ1718 / TOI2010初選(prob 3)。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536