2222 . 校慶紀念品
TopCoder
Tags
Description
又到了購買校慶紀念品的季節，今年學生會推出了 $N$ 種校慶紀念品，第 $i$ 種紀念品的價錢是一個 $w_i$ 元，並且受歡迎度是 $v_i$。每一種紀念品學生會都做了很多，所以不用擔心會買不到。
你打算要買一些校慶紀念品作為送給校隊培訓講師的禮物，你知道一個人絕對不會想收到兩個同樣種類的校慶紀念品，因此對於某一種校慶紀念品，你只能送給一個講師最多一個。還有為了避免差別待遇，你打算送每一個講師相同的紀念品。為了盡量讓講師們開心，你希望你送的紀念品的受歡迎度總和盡量大。
正式地說，如果講師有 $k$ 人，並且你打算送他們第 $a_1,a_2,\dots,a_t$ 種校慶紀念品，那麼對於 $1 \leq i \leq t$，你必須要準備 $k$ 份第 $a_i$ 種校慶紀念品，每個講師各送一個。而你送的紀念品的受歡迎度總和是 $\sum_{i=1}^ t v_{a_i} \times k$。
不過，你的錢包裡只有 $M$ 元，而且你現在還不知道校隊培訓講師有幾個人，你只知道講師的人數在 $[1,K]$ 之間，在調查清楚講師到底有幾個人之前，你想事先知道對於所有 $1 \leq k \leq K$，如果講師有 $k$ 個人的話，你送出的紀念品的受歡迎度總和最大可以是多少。
測資限制
- $1 \leq N,M,K \leq 10^ 4$
- $1 \leq w_i \leq M$
- $1 \leq v_i \leq 10^ 9$
Input Format
第一行有三個整數 $N,M,K$，分別表示校慶紀念品的種類數、你有多少錢和講師人數的最大值。
接下來有 $N$ 行，其中第 $i$ 行有兩個整數 $w_i,v_i$，分別表示第 $i$ 種校慶紀念品的價格和受歡迎度。
Output Format
輸出 $K$ 行，第 $i$ 行包含一個數字，表示若講師人數為 $i$，你送出的紀念品受歡迎度總和最大可以是多少。
Sample Input 1
3 5 4
2 4
3 2
1 1
2 4
3 2
1 1
Sample Output 1
6
8
3
4
8
3
4
Sample Input 2
7 42 10
5 10
7 2
7 6
2 6
5 2
3 5
2 2
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
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 | $N \le 20, K \le 10$ | 5 |
| 3 | 10~18 | $K = 1$ | 14 |
| 4 | 19~24 | $w_i = 1$ | 17 |
| 5 | 0~30 | 無額外限制 | 64 |