0 Judge
Code: 0
你現在正在一間吃到飽餐廳,有很多的食物可以讓你吃到飽,為了回本當然是希望能盡量吃多一些啊。但是有些食物雖然可以讓你吃很飽,但味道卻爛得跟斯大林一樣,滿足感就會比較低,而你的胃容量又有限制,因此你想在不超過胃容量的情況下獲得最大的滿足感。
你看到架子上有$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$。
對於每筆測資,輸出你能獲得的滿足感最大值。