一公斤金坷垃原料高達五百萬美元

題目敘述

想必各位一定知道，一公斤金坷垃原料高達五百萬美元。在金坷垃生產基地，美國聖地牙哥國際農業集團，存放了各種不同體積和價值的金坷垃原料。首席科學家會把這些原料放入一個最多能裝$M$單位體積的容器中，因為原料是一塊一塊的，所以放入時不能分割，將各種原料混合在一起就能產生新的原料。但是現在有個問題，因為容器的體積有限，科學家們想要讓製造出來的新原料越貴越好，請問製造出來的新原料最貴的價格是多少?
(假設每一種原料都無限供應，也就是容器裡面可以放好幾塊相同種類的原料)

輸入說明

第一行有兩個數字$N,M$，$1 \leq N \leq 100, \; 1 \leq M \leq 10000 $，接著有$N$行，每行有兩個正整數$w_i,c_i$，$1 \leq w_i \leq 10000, \; 1 \leq c_i \leq 5000000$，表示第$i$種原料每塊的體積為$w_i$，價格為$c_i$

輸出說明

請輸出製造出來的新原料最貴的價格是多少

範例輸入1

範例輸出1

範例輸入2

範例輸出2

提示

容器沒有規定要塞滿

範例測資1中，第二種原料我們拿五塊放入容器，可以達到最大價格3*5=15

範例測資2中，第一種和第二種原料我們各取一塊放入容器中，可以達到最大價格2+7=9

Judge Setting

run-time limit: 20 ms
memory limit: 913104 byte
測資數量: 0