Description

阿星是神偷專業協會 (Thief Professional Committee) 的會員之一，這個協會每年都會舉辦一次偷盜大賽，比賽的規則如果

1. 每位參賽者會發配一個有限空間的黑色布袋，假設該布袋容量為R，一旦裝太多東西，很有可能會被警察抓到，所以身為一個專業的小偷是不會讓自己超載。
2. 每個人都可以從任務欄上選一張收藏品清單，清單裡面有每個博物館收藏品的大小以及該物品的價值
3. 比賽限時一個晚上，統計出每位參賽者總共偷了價值多少的收藏品
4. 而偷到收藏品價值總和最多的會員，就是該年度的MVP

阿星很想要得到這個稱號來證明自己高超的偷術，但是他不知道要怎麼樣才能在不超載（收藏品總大小不超過R）的情況下，哪一張清單才能偷到總價值最多的收藏品，他希望你能告訴他每一張清單在總大小R以內最多可以的收藏品總價值。

Input

第一行表示公佈欄上有T (T <= 100)張清單，以及布袋容量R (R <= 100)

接下來每一張清單的第一行有一個數字N (N <= 100)表示清單上有N個收藏品，之後的N行中，每行都有兩個數字W_i (1 <= W_i <= 100), V_i  (1 <= V_i <= 1,000,000)表示該收藏品的大小以及價值。

Output

每一行都要輸出“List i: value”的形式，其中i表示第i張清單，value表示這張清單中可以偷取最多總價值多少的收藏品，詳情請看Sample Output

Sample Input  Download

Sample Output  Download

Tags

Discuss