0 Judge
Code: 0
你現在正在一間吃到飽餐廳,有很多的食物可以讓你吃到飽,為了回本當然是希望能盡量吃多一些啊。但是有些食物雖然可以讓你吃很飽,但味道卻爛得跟斯大林一樣,滿足感就會比較低,而你的胃容量又有限制,因此你想在不超過胃容量的情況下獲得最大的滿足感。
你看到架子上有$N$個食物,你分析了分別吃這$N$個食物可以獲得的飽足感跟滿足感,請問再不超過胃容量限制的情況下,你最多可以獲得多少滿足感呢?
第一行為一個正整數$T(T \leq 10$,表示共有$T$筆測資。 每筆測資第一行為兩個正整數$N,M$,表示食物的數量及你可以承受的飽足感上限,$1 \leq N \leq 100$,$1 \leq M \leq 1000000$。
接著$N$行,每行為兩個正整數$A_i,B_i$,表示吃掉第$N$個食物可以獲得的飽足感與滿足感,$1 \leq A_i \leq 100000$,$1 \leq B_i \leq 100$。
對於$30\%$的測資,$Ai \leq 100$。
對於每筆測資,輸出你在飽足感不超過$M$時能獲得的滿足感最大值。