2181 . 表演節目 (Show)
TopCoder
Description
資訊能力競賽頒獎典禮將安排一定數量以上的社團進行表演。小朱是這次活動的總策劃，由於臺北市有許多優秀的表演社團，他蒐集過去社團表演的數據，經統計分析後，初步篩選出具有高人氣指標的社團，以及該表演的演出費用。請幫助小朱計算在不超過表演總預算的前提下，可邀請表演的社團組合中，社團人氣指標總和最高為多少，並計算其表演所需總費用。
Input Format
第一行為二個以空白為間隔之正整數 $a, N$，分別代表「表演總預算 $a$ 千元」($5 \leq a \leq 1000$)，以及「可被邀請進行表演之社團數量 $N$」($1 \leq N \leq 1000$)。
第$2$至第$N+1$行，分別列出社團編號$1$至$N$相關資訊，每一行有兩個以空白為間隔的正整數，分別為該社團表演的人氣指標 $x$ ($1 \leq x \leq 100$) 及演出費用 $y$ 千元 ($1 \leq y \leq 100$)。
Output Format
輸出一行兩個整數 $M, S$，分別代表在表演總預算額度內，可邀請表演社團組合中，社團人氣指標總和最高為 $M$，且該社團組合表演所需總費用需 $S$ 千元。
Sample Input 1
5 3
16 1
58 4
47 3
16 1
58 4
47 3
Sample Output 1
74 5
Sample Input 2
7 6
16 2
36 1
85 2
23 2
30 1
66 2
16 2
36 1
85 2
23 2
30 1
66 2
Sample Output 2
217 6
Hints
本題共有四組測試資料，每組可有多筆測試資料：
第一、二組測試資料，$5 \leq a \leq 10, 1 \leq N \leq 10$，各 20 分；
第三、四組測試資料，$5 \leq a \leq 1000, 1 \leq N \leq 1000$，各 30 分。
註：原題沒有標明如果有多種方案可以得到最高人氣指標，應該輸出哪一個方案的成本。本題請輸出所有最高人氣指標的方案中，成本最低的方案的成本即可。
Problem Source
107北市賽
testdata set by Omelet
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $5 \leq a \leq 10, 1 \leq N \leq 10$ | 20 |
| 2 | 10~19 | $5 \leq a \leq 10, 1 \leq N \leq 10$ | 20 |
| 3 | 0~9, 20~29 | $5 \leq a \leq 1000, 1 \leq N \leq 1000$ | 30 |
| 4 | 10~19, 30~39 | $5 \leq a \leq 1000, 1 \leq N \leq 1000$ | 30 |