2181 . 表演節目 (Show)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

95.1% (77/81)

Submission's AC Ratio

54.1% (119/220)

Tags

北市賽 2018-北市賽

Description

資訊能力競賽頒獎典禮將安排一定數量以上的社團進行表演。小朱是這次活動的總策劃，由於臺北市有許多優秀的表演社團，他蒐集過去社團表演的數據，經統計分析後，初步篩選出具有高人氣指標的社團，以及該表演的演出費用。請幫助小朱計算在不超過表演總預算的前提下，可邀請表演的社團組合中，社團人氣指標總和最高為多少，並計算其表演所需總費用。

Input Format

第一行為二個以空白為間隔之正整數 a,N，分別代表「表演總預算 a 千元」(5≤a≤1000)，以及「可被邀請進行表演之社團數量 N」(1≤N≤1000)。
第2至第N+1行，分別列出社團編號1至N相關資訊，每一行有兩個以空白為間隔的正整數，分別為該社團表演的人氣指標 x (1≤x≤100) 及演出費用 y 千元 (1≤y≤100)。

Output Format

輸出一行兩個整數 M,S，分別代表在表演總預算額度內，可邀請表演社團組合中，社團人氣指標總和最高為 M，且該社團組合表演所需總費用需 S 千元。

Sample Input 1

5 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

Sample Output 2

217 6

Hints

本題共有四組測試資料，每組可有多筆測試資料：
第一、二組測試資料，5≤a≤10,1≤N≤10，各 20 分；
第三、四組測試資料，5≤a≤1000,1≤N≤1000，各 30 分。

註：原題沒有標明如果有多種方案可以得到最高人氣指標，應該輸出哪一個方案的成本。本題請輸出所有最高人氣指標的方案中，成本最低的方案的成本即可。

Problem Source

107北市賽
testdata set by Omelet

Subtasks

No. Testdata Range Constraints Score
1 0~9 5≤a≤10,1≤N≤10 20
2 10~19 5≤a≤10,1≤N≤10 20
3 0~9, 20~29 5≤a≤1000,1≤N≤1000 30
4 10~19, 30~39 5≤a≤1000,1≤N≤1000 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Submit
Back to Top