TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

94.9% (37/39)

Submission's AC Ratio

60.7% (68/112)

Tags

Description

又到了購買校慶紀念品的季節,今年學生會推出了 N 種校慶紀念品,第 i 種紀念品的價錢是一個 wi 元,並且受歡迎度是 vi。每一種紀念品學生會都做了很多,所以不用擔心會買不到。

你打算要買一些校慶紀念品作為送給校隊培訓講師的禮物,你知道一個人絕對不會想收到兩個同樣種類的校慶紀念品,因此對於某一種校慶紀念品,你只能送給一個講師最多一個。還有為了避免差別待遇,你打算送每一個講師相同的紀念品。為了盡量讓講師們開心,你希望你送的紀念品的受歡迎度總和盡量大。

正式地說,如果講師有 k 人,並且你打算送他們第 a1,a2,,at 種校慶紀念品,那麼對於 1it,你必須要準備 k 份第 ai 種校慶紀念品,每個講師各送一個。而你送的紀念品的受歡迎度總和是 i=1tvai×k

不過,你的錢包裡只有 M 元,而且你現在還不知道校隊培訓講師有幾個人,你只知道講師的人數在 [1,K] 之間,在調查清楚講師到底有幾個人之前,你想事先知道對於所有 1kK,如果講師有 k 個人的話,你送出的紀念品的受歡迎度總和最大可以是多少。

測資限制

  • 1N,M,K104
  • 1wiM
  • 1vi109

Input Format

第一行有三個整數 N,M,K,分別表示校慶紀念品的種類數、你有多少錢和講師人數的最大值。

接下來有 N 行,其中第 i 行有兩個整數 wi,vi,分別表示第 i 種校慶紀念品的價格和受歡迎度。

Output Format

輸出 K 行,第 i 行包含一個數字,表示若講師人數為 i,你送出的紀念品受歡迎度總和最大可以是多少。

Sample Input 1

3 5 4
2 4
3 2
1 1

Sample Output 1

6
8
3
4

Sample Input 2

7 42 10
5 10
7 2
7 6
2 6
5 2
3 5
2 2

Sample Output 2

33
58
69
84
80
96
77
88
72
80

Hints

對於第一筆範測:

  • 當講師有 1 人時,送每人第 1,2 種紀念品。
  • 當講師有 2 人時,送每人第 1 種紀念品。
  • 當講師有 3 人時,送每人第 3 種紀念品。
  • 當講師有 4 人時,送每人第 3 種紀念品。

Problem Source

2021 師大附中校隊培訓 模擬競賽

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~9 N20,K10 5
3 10~18 K=1 14
4 19~24 wi=1 17
5 0~30 無額外限制 64

Testdata and Limits

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