Bored during the vacation, Eric decided to develop and play a game called Carrot Click Game, and the rules are as follows:

In this game, Eric initially starts the game with $0$ carrots and $s$ equal to $1$.

Then, every second, he can take one of two actions:

1. Click and get $s$ carrots.
2. Choose an integer $i$ $(1 \le i \le N)$. Then, pay $A_i$ of the carrots you have and buy the $i$-th speed effect. In this case, $s$ is increased by $B_i$. (You can also buy again a previously bought speed effect).

Let's help Eric, who has exhausted all his energy developing the game, by finding out how many carrots he can obtain after playing the game for $K$ seconds!

Input

The first line contains two space-separated integers $N$ and $K$.

The $i$-th line of the following $N$ lines contains two space-separated integers $A_i$ and $B_i$.

Output

Print the maximum number of carrots that can be obtained after playing the game for $K$ seconds.

Constraints

• $1\le N,K\le 100$
• $1\le A_i,B_i\le 50$

Scoring

Examples

Input 1

2 4
1 2
2 5

Output 1

6