Chocolate Buying

Bessie and the herd love chocolate, so Farmer John is buying them some.

The chocolate store carries $N$ ($1 \le N \le 100{,}000$) kinds of chocolate, each available in essentially unlimited quantity. Each type $i$ costs $P_i$ ($1 \le P_i \le 10^{18}$) per piece, and there are $C_i$ ($1 \le C_i \le 10^{18}$) cows that want that type.

Farmer John has a budget of $B$ ($1 \le B \le 10^{18}$) to spend on chocolate for the cows. What is the maximum number of cows he can satisfy? Every cow wants exactly one type of chocolate and is satisfied only by that type.

For example, suppose Farmer John has 50 to spend across 5 types of chocolate. Eleven cows in total have the following preferences:

Farmer John cannot buy chocolate type 5, because he does not have enough money. Even if it cost only 50, it would be a wasteful purchase, since it would satisfy just one cow.

Starting from the cheapest chocolate, he can buy 1 piece of type 2 for $1 \times 1 = 1$, leaving $50 - 1 = 49$; then 3 pieces of type 1 for $3 \times 5 = 15$, leaving $49 - 15 = 34$; then 2 pieces of type 4 for $2 \times 7 = 14$, leaving $34 - 14 = 20$; then 2 pieces of type 3 for $2 \times 10 = 20$, leaving $20 - 20 = 0$.

He therefore satisfies $1 + 3 + 2 + 2 = 8$ cows.

• Line 1: Two space-separated integers, $N$ and $B$.
• Lines 2 to $N+1$: Line $i$ contains two space-separated integers describing chocolate type $i$: $P_i$ and $C_i$.

• Line 1: A single integer, the maximum number of cows that Farmer John can satisfy.