問題文

一人暮らしを始めた Kite_kuma くんは、 これから $D$ 日間夕食の自炊を行うことに決めました。

はじめ、 Kite_kuma くんの元気度は $0$ です。毎日の自炊では、 $N$ 種類の料理の中から一つを選択し、調理した後食べます。$i$ 番目の料理を調理すると元気度が $P_i$ 減少し、その後料理を食べることで元気度が $Q_i$ 増加します。ただし同じ種類の料理を連続で食べると飽きてしまうので、そのような料理の選び方は禁止されています。

Kite_kuma くんは常に元気でいたいので、 $D$ 日間の中での元気度の最小値を最大化するように行動します。
以上の条件のもとで、 $D$ 日間の中での Kite_kuma くんの元気度の最小値を求めてください。ただし Kite_kuma くんの元気度は夕食の自炊でのみ変化するものとします。

制約

入力

$N$ $D$
$P_1$ $Q_1$
$P_2$ $Q_2$
$⋮$
$P_N$ $Q_N$

出力

条件のもとでの、$D$ 日間の中での Kite_kuma くんの元気度の最小値を出力してください。

サンプル

2 2
3 3
1 2

-2