Little X has opened a candy store that sells $n$ types of candy, with an infinite supply of each type. Little X uses different promotional strategies for different types of candy. Specifically, for the $i$-th ($1 \le i \le n$) type of candy, the price of the first piece is $x_i$, the second is $y_i$, the third is $x_i$ again, the fourth is $y_i$, and so on.

Little R has $m$ units of money to buy candy. Little R does not care about the type of candy and only wants to get as many pieces of candy as possible. You need to help Little R find the maximum number of pieces of candy that can be purchased with $m$ units of money.

Input

The first line contains two positive integers $n$ and $m$, representing the number of candy types and the amount of money Little R has.

The $(i+1)$-th line ($1 \le i \le n$) contains two positive integers $x_i$ and $y_i$, representing the price of the odd-numbered pieces and the even-numbered pieces of the $i$-th type of candy, respectively.

Output

Output a single non-negative integer representing the maximum number of pieces of candy that can be purchased with $m$ units of money.

Examples

Input 1

1 10
4 1

Output 1

4

Note 1

Little R can buy 4 pieces of the first type of candy, costing $4 + 1 + 4 + 1 = 10$.

Input 2

3 15
1 7
2 3
3 1

Output 2

8

Note 2

Little R can buy 1 piece of the first type, 1 piece of the second type, and 6 pieces of the third type, costing $1 + 2 + 12 = 15$.

Examples 3-7

See the files candy/candy3.in through candy/candy7.in and their corresponding .ans files in the contestant's directory. These examples satisfy the constraints of the specified test cases.

Constraints

For all test data, we have: $1 \le n \le 10^5$ $1 \le m \le 10^{18}$ * For all $1 \le i \le n$, $1 \le x_i, y_i \le 10^9$

Special Property A: For all $1 \le i \le n$, $x_i = y_i$. Special Property B: For all $1 \le i \le n$, $x_i \ge y_i$.