User's AC Ratio

64.7% (11/17)

Submission's AC Ratio

22.9% (22/96)

Description

你和你的朋友黃鰭鮪魚現在來到一間蛋糕店,這間蛋糕店有許多的蛋糕。
每個蛋糕有各自的特色,有些蛋糕的裝飾比較華麗,
有些的味道則比較好吃,而每個蛋糕的價格也不盡相同。
因為每個人的喜好不同,所以對於這些蛋糕的喜好度也不同。

現在定義了一個叫做好吃度的數值,
假設某塊蛋糕的好吃度為 $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$ 元,他給每個蛋糕的好吃度與各自的價格,
想請你跟他說他最多可以獲得多少滿足感。

Input Format

輸入第一行有兩個整數 $N,K$,分別代表蛋糕的數量以及黃鰭鮪魚現在身上有多少錢。
接下來有 $N$ 行,每行有兩個整數 $d,c$,代表那塊蛋糕的好吃度及價格。
每一塊蛋糕都只能購買一次。

  • $1\leq N\leq2\times10^5$
  • $0\leq K,d,c\leq10^9$

Output Format

輸出一個數字,代表黃鰭鮪魚最多可以獲得的滿足感為多少。
只要你的答案 $oup$ 跟正確答案 $ans$ 符合以下公式,你的答案就會被算做正確。
$$
\frac{\lvert oup-ans\rvert}{\max(ans,1)}\leq10^{-6}
$$

Sample Input 1

5 5
6 3
4 8
12 6
4 2
9 2

Sample Output 1

15

Sample Input 2

3 2
1 10
6 6
5 3

Sample Output 2

3.33333333

Sample Input 3

3 100
1 10
6 6
5 3

Sample Output 3

12

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~30 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1
23 1000 65536 65536 1
24 1000 65536 65536 1
25 1000 65536 65536 1
26 1000 65536 65536 1
27 1000 65536 65536 1
28 1000 65536 65536 1
29 1000 65536 65536 1
30 1000 65536 65536 1