TopCoder

Thumb screenshot from 2022 02 07 14 53 28
FHVirus
$\Huge 8e7 二分圖判斷範例程式碼有錯,道歉!$

User's AC Ratio

96.3% (26/27)

Submission's AC Ratio

75.3% (55/73)

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

// Sample input 1
3 5 4
2 4
3 2
1 1

// Sample input 2
7 42 10
5 10
7 2
7 6
2 6
5 2
3 5
2 2

Sample Output

// Sample output 1
6
8
3
4

// 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 $N \le 20, K \le 10$ 5
3 10~18 $K = 1$ 14
4 19~24 $w_i = 1$ 17
5 0~30 無額外限制 64

Testdata and Limits

No. Time Limit (ms) Memory Limit (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