TopCoder

AaW
學弟電爛我了

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

52.4% (11/21)

Tags

Description

你吃過「大根蘿蔔」嗎?
img
據說,有一種非常大根的蘿蔔,叫作「大根蘿蔔」。由於大根蘿蔔不需特別施肥就會長得肥美,因此是許多農夫愛種的作物之一。

今年,由於天氣天氣特別冷,蘿蔔的收成特別好。身為專業披薩外送小哥的Brine,聽說這個消息之後,為了開發新口味的披薩,便特地跑到田鼠的農場去吃蘿蔔。

身為一個專業的農夫,田鼠準備了$n$根最甜的大根蘿蔔要給Brine吃。但是,大根蘿蔔實在是太大根了,Brine的胃裝不下全部。
已知第i根大根蘿蔔的總甜度為$a_i$,而體積為$b_i$單位。另外,Brine的胃總共可以吃$m$單位的蘿蔔。請問Brine吃到的蘿蔔總甜度最多可以多高?
順帶一提的是,蘿蔔是可以切開來的喔,而如果Brine只吃了$\frac{b_i}{k}$單位的蘿蔔,他會吃到$\frac{a_i}{k}$單位的甜度。

Input Format

$n\;m$
$a_1\;b_1$
$a_2\;b_2$
...
$a_n\;b_n$

範圍:
$1 < n < 10$5
$m,\,a_i,\,b_i$在int範圍內

Output Format

請輸出一個整數,代表Brine能吃到多少甜度的蘿蔔。
若為小數,請將答案無條件捨去到整數。

Sample Input 1

2 5
50 10
5 5

Sample Output 1

25

Hints

大根蘿蔔好吃

Problem Source

Problem Statement from TIOJ1908

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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