有$n$杯糖水，第$i$杯糖水是由$g_i$公克的糖加水製成的$v_i$毫升的糖水。現在你有一個容量為$V$的大杯子，你可以從那$n$杯糖水任意的倒入大杯子中(每杯糖水可以選擇不使用，全部倒完，或者只倒一部分)，之後你將大杯子拿去做蒸發結晶法(將水蒸發煮乾使得糖結晶析出)，請問你最多能得到多少公克的糖?
多筆測資，第一行有一個整數$n$，若讀到$n=0$代表測資結束，不須對此筆輸入做出任何輸出。
接下來有$n$行每行兩個正整數$g_i,v_i$，分別代表含糖重與容量。
最後一行有一個正整數$V$為大杯子的容量。
20%測資符合$n\le 20$
40%測資符合$n\le 1000$
100%測資符合$n\le 10^5,1\le g_i,v_i\le 10^5,1\le V\le 10^9$且保證$g_i$是$v_i$的倍數
每個測資點不超過$5$筆測資。
每筆測資輸出一個數字代表最多能得到的糖重量。
5 3 3 4 2 3 1 8 4 6 2 8 0
19
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||