Problem Statement

Kite_kuma, who has started living alone, has decided to cook his own dinner for the next $D$ days.

Initially, Kite_kuma's energy level is $0$. Each day, he chooses one of $N$ types of dishes, cooks it, and then eats it. Cooking the $i$-th dish decreases his energy level by $P_i$, and then eating the dish increases his energy level by $Q_i$. However, since he would get tired of eating the same type of dish on consecutive days, such a choice of dishes is forbidden.

Kite_kuma always wants to stay energetic, so he acts so as to maximize the minimum value of his energy level during the $D$ days.
Under the above conditions, find the minimum value of Kite_kuma's energy level during the $D$ days. Assume that Kite_kuma's energy level changes only through cooking and eating his dinners.

Constraints

Input

$N$ $D$
$P_1$ $Q_1$
$P_2$ $Q_2$
$\vdots$
$P_N$ $Q_N$

Output

Print the minimum value of Kite_kuma's energy level during the $D$ days under the given conditions.

Sample

2 2
3 3
1 2

-2