Talent Show

Time limit2sMemory limit512 MB

Summary

Choose a group of cows with total weight at least W maximizing the ratio of total talent to total weight, and print floor(1000A).

Level: Medium6 of 10
Topics: Dynamic programming, Binary search, Greedy
Solved: No attempts yet

Problem

Farmer John brings his $N$ cows, numbered $1$ through $N$ , to the county fair for the annual bovine talent show. Cow $i$ has weight $w_i$ and talent level $t_i$ , both integers.

The rules of this year's show are new.

(i) The group of cows entered into the show must have total weight at least $W$ . The rule exists so that one outstanding cow cannot win on its own.

(ii) The group with the largest ratio of total talent to total weight wins.

All of Farmer John's cows together weigh at least $W$ , so a group satisfying rule (i) always exists. Determine the largest ratio of total talent to total weight he can reach with such a group.

Input

The first line contains $N$ ( $1 \le N \le 250$ ) and $W$ ( $1 \le W \le 1000$ ). Each of the next $N$ lines describes one cow with two integers $w_i$ ( $1 \le w_i \le 10^6$ ) and $t_i$ ( $1 \le t_i \le 10^3$ ).

Output

Let $A$ be the largest ratio of total talent to total weight reachable by a group whose total weight is at least $W$ . Print the floor of $1000A$ , which keeps the output integer. The floor operation discards the fractional part and rounds down to an integer, and leaves a value that is already an integer unchanged.

Hint

In the first example the best ratio for a single cow belongs to the cow with talent 11 and weight 10. The group needs total weight at least 15, so the best group adds the cow with talent 21 and weight 20. That group has ratio $(11+21)/(10+20) = 32/30 = 1.0666\ldots$ , and multiplying by 1000 and taking the floor gives 1066.

Examples3

Example 1
Input
```
3 15
20 21
10 11
30 31
```
Expected output
```
1066
```
Example 2
Input
```
1 1
1 1000
```
Expected output
```
1000000
```
Example 3
Input
```
1 3
3 1
```
Expected output
```
333
```