Carrot Click Game

Eric had too much free time during his vacation, so he decided to make a game called Carrot Click Game and play it himself.

At the start of the game, Eric has 0 carrots and $s$ is 1.

Every second, he can do one of the following two actions.

1. Click the mouse to get $s$ carrots.
2. Choose an integer $i$ ($1 \le i \le N$) and pay $A_i$ carrots to buy the $i$-th speed effect. Right after the purchase, $s$ increases by $B_i$. (A speed effect bought earlier can be bought again.)

Eric used up all his energy building the game, so find the maximum number of carrots he can have after playing for $K$ seconds.

The first line contains two integers $N$ and $K$, separated by a space.

Each of the next $N$ lines contains two integers $A_i$ and $B_i$, separated by a space, for the $i$-th speed effect.

Print the maximum number of carrots Eric can have after playing the game for $K$ seconds.

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