Bovine Chocolate Satisfaction

Farmer John wants to satisfy as many cows as possible with chocolates. There are (N) kinds of chocolate available at the Bovine Chocolate Store, and each type (i) has a price (P_i) per piece and is desired by (C_i) cows. Farmer John has a total budget of (B). Each cow will only be satisfied if it receives the chocolate of its preferred type, and each cow only needs one piece of chocolate.

In order to maximize the number of satisfied cows, Farmer John can choose to buy some or all of the chocolates of each type such that the total spending does not exceed (B). The optimal strategy is to purchase chocolates starting with the cheapest type, satisfying as many cows as possible with that type, and then moving on to the next cheapest type.

Given (N), (B), and for each chocolate type its cost (P_i) and the number of cows (C_i) that need it, determine the maximum number of cows Farmer John can satisfy.

inputFormat

The first line contains two integers (N) and (B) ((1 \leq N \leq 100,000), (1 \leq B \leq 10^{18})). Each of the next (N) lines contains two integers (P_i) and (C_i) ((1 \leq P_i \leq 10^{18}), (1 \leq C_i \leq 10^{18})), representing the price per chocolate and the number of cows that prefer this type, respectively.

outputFormat

Output a single integer, the maximum number of cows that can be satisfied without exceeding the budget (B).

sample

5 50
5 3
1 1
10 4
7 2
60 1

8