你和你的朋友黃鰭鮪魚現在來到一間蛋糕店,這間蛋糕店有許多的蛋糕。
每個蛋糕有各自的特色,有些蛋糕的裝飾比較華麗,
有些的味道則比較好吃,而每個蛋糕的價格也不盡相同。
因為每個人的喜好不同,所以對於這些蛋糕的喜好度也不同。
現在定義了一個叫做好吃度的數值,
假設某塊蛋糕的好吃度為 $d$,代表在吃掉這塊蛋糕後,
會獲得 $d$ 的滿足感。
這家店的蛋糕是可以只購買一部份的,如果你只有吃整塊蛋糕的一部分,
則只能獲得一部分的滿足感,獲得的滿足感與你吃的量呈線性關係。
當然所需要支付的價格也是與你吃的量呈線性關係。
舉例來說,假設有一塊好吃度為 $d$,且價格為 $c$ 的蛋糕,
若你吃了整塊的 $\frac{1}{3}$,則你需花費 $\frac{1}{3}c$ 購買蛋糕,且你會獲得 $\frac{1}{3}d$ 的滿足感;
若你吃了整塊的 $\frac{3}{5}$,則你需花費 $\frac{3}{5}c$ 購買蛋糕,且你會獲得 $\frac{3}{5}d$ 的滿足感。
黃鰭鮪魚現在身上有 $K$ 元,他給每個蛋糕的好吃度與各自的價格,
想請你跟他說他最多可以獲得多少滿足感。
輸入第一行有兩個整數 $N,K$,分別代表蛋糕的數量以及黃鰭鮪魚現在身上有多少錢。
接下來有 $N$ 行,每行有兩個整數 $d,c$,代表那塊蛋糕的好吃度及價格。
每一塊蛋糕都只能購買一次。
輸出一個數字,代表黃鰭鮪魚最多可以獲得的滿足感為多少。
只要你的答案 $oup$ 跟正確答案 $ans$ 符合以下公式,你的答案就會被算做正確。
$$
\frac{\lvert oup-ans\rvert}{\max(ans,1)}\leq10^{-6}
$$
No. | Testdata Range | Score |
---|---|---|
1 | 0~30 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 | |
24 | 1000 | 65536 | 65536 | |
25 | 1000 | 65536 | 65536 | |
26 | 1000 | 65536 | 65536 | |
27 | 1000 | 65536 | 65536 | |
28 | 1000 | 65536 | 65536 | |
29 | 1000 | 65536 | 65536 | |
30 | 1000 | 65536 | 65536 |