Problem Description

Takahashi has decided to get his summer homework done.

The homework consists of $N$ problems numbered from $1$ to $N$. Solving problem $i$ takes $2^{A_i}$ seconds and yields $B_i$ points.

Takahashi needs to solve the problems such that the total points obtained is at least $K$. Find the minimum time required to achieve this.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ A_1 $ $ B_1 $ $ : $ $ A_{N} $ $ B_{N} $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

6 24
1 5
0 4
1 9
2 10
2 11
3 15

Sample Output #1

7

Sample Input #2

13 105
0 1
3 8
5 28
0 1
0 2
4 17
5 26
5 33
3 8
4 19
3 7
2 4
4 17

Sample Output #2

98

Sample Input #3

5 5000000000
30 1000000000
30 1000000000
30 1000000000
30 1000000000
30 1000000000

Sample Output #3

5368709120

Notes/Hints

Constraints

• $1 \leq N \leq 10^{5}$
• $0 \leq A_i \leq 30$
• $1 \leq B_i \leq 10^{9}$
• $1 \leq K \leq \Sigma{B_i}$
• All given inputs are integers

Sample Explanation 1

• Solving problems $2, 3, 5$ yields $24$ points in $7$ seconds, which is optimal.

Sample Explanation 3

• Note that the answer can be very large.

见题面 Input 部分

见题面 Output 部分