TopCoder

Thumb fhvirus
FHVirus
$\huge{都去寫酷酷新題}$

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

50.0% (18/36)

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

輸入範例 2
7 6
16 2
36 1
85 2
23 2
30 1
66 2

Sample Output

輸出範例 1
74 5

輸出範例 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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 3
1 1000 524288 65536 1 3
2 1000 524288 65536 1 3
3 1000 524288 65536 1 3
4 1000 524288 65536 1 3
5 1000 524288 65536 1 3
6 1000 524288 65536 1 3
7 1000 524288 65536 1 3
8 1000 524288 65536 1 3
9 1000 524288 65536 1 3
10 1000 524288 65536 2 4
11 1000 524288 65536 2 4
12 1000 524288 65536 2 4
13 1000 524288 65536 2 4
14 1000 524288 65536 2 4
15 1000 524288 65536 2 4
16 1000 524288 65536 2 4
17 1000 524288 65536 2 4
18 1000 524288 65536 2 4
19 1000 524288 65536 2 4
20 1000 524288 65536 3
21 1000 524288 65536 3
22 1000 524288 65536 3
23 1000 524288 65536 3
24 1000 524288 65536 3
25 1000 524288 65536 3
26 1000 524288 65536 3
27 1000 524288 65536 3
28 1000 524288 65536 3
29 1000 524288 65536 3
30 1000 524288 65536 4
31 1000 524288 65536 4
32 1000 524288 65536 4
33 1000 524288 65536 4
34 1000 524288 65536 4
35 1000 524288 65536 4
36 1000 524288 65536 4
37 1000 524288 65536 4
38 1000 524288 65536 4
39 1000 524288 65536 4