問題文

$N$ 個の等差数列があります。$i$ 個目の等差数列は初項 $A_i$ 、公差 $D_i$ 、項数 $10^{100}$ です。

長さ $N$、総和 $M$ の非負整数列 $X = (X_1, X_2, \dots, X_N)$ に対して、$X$ のスコア $f(X)$ を次の通り定めます。

• $\displaystyle f(X) = \sum_{i = 1}^{N}$ （ $i$ 個目の等差数列の先頭 $X_i$ 項の総和）

ただし、先頭 $0$ 項の総和は $0$ であると定めます。

長さ $N$、総和 $M$ の非負整数列 $X$ を自由に選べるとき、$f(X)$ の値として考えられる最大値を求めてください。

制約

• 入力は全て整数
• $2 \leq N \leq 3 \times 10^5$
• $1 \leq M \leq 3 \times 10^5$
• $-10^7 \leq A_i, D_i \leq 10^7$

入力

入力は標準入力から以下の形式で与えられる。

$N$ $M$
$A_1$ $D_1$
$\vdots$
$A_N$ $D_N$

出力

$f(X)$ の最大値を出力せよ。この問題の制約下で、答えの絶対値は $2^{63}$ 未満であることが示せる。

3 5
1 2
-8 5
13 -7

29

2 10
-100 -100
-10 0

-100

5 2000
4005698 -1849641
3217860 -4274311
9504793 -3809644
-1590549 2314
2581917 -3604118

1454884836