229. 吃到飽問題2

0 Judge

Code: 0


吃到飽問題2

你現在正在一間吃到飽餐廳,有很多的食物可以讓你吃到飽,為了回本當然是希望能盡量吃多一些啊。但是有些食物雖然可以讓你吃很飽,但味道卻爛得跟斯大林一樣,滿足感就會比較低,而你的胃容量又有限制,因此你想在不超過胃容量的情況下獲得最大的滿足感。

你看到架子上有$N$個食物,你分析了分別吃這$N$個食物可以獲得的飽足感跟滿足感,這時候老闆走過來,她覺得你上次在這裡吃太多東西了,所以這次她限制你最多只能吃$K$個食物

請問再不超過胃容量限制和老闆的限制的情況下,你最多可以獲得多少滿足感呢?

輸入說明

第一行為一個正整數$T(T \leq 10$,表示共有$T$筆測資。 每筆測資第一行為兩個正整數$N,M,K$,表示食物的數量、你可以承受的飽足感上限,還有老闆限制你吃的食物數量,$1 \leq K \leq N \leq 100$,$1 \leq M \leq 1000$。

接著$N$行,每行為兩個正整數$A_i,B_i$,表示吃掉第$N$個食物可以獲得的飽足感與滿足感,$1 \leq A_i \leq 100$,$1 \leq B_i \leq 1000000$。

對於$30\%$的測資,$K=N$。

輸出說明

對於每筆測資,輸出你能獲得的滿足感最大值。

範例輸入

範例輸出


Judge Setting

run-time limit: 85 ms
memory limit: 131072 byte
測資數量: 0