题目描述

有三个数列 $A,B,C$。

其中 $C$ 表示为 $x_1,\ \dots,\ x_N,\ y_1,\ \dots,\ y_N$ 的形式，意思是前 $y_1$ 个数为 $x_1$,之后 $y_2$ 个数为 $x_2$……最后 $y_N$ 个数为 $x_N$。

$B$ 为 $C$ 的前缀和数组。

$A$ 为 $B$ 的前缀和数组。

求 $A$ 中最大值。

输入格式

对于每组数据，

第一行为两个数 $N$ 和 $M$，

第 $2$ 至 $N+1$ 行，第 $i$ 行为两个数 $x_{i-1}$ 和 $y_{i-1}$。

输出格式

对于每组数据，输出一行一个整数表示答案

样例 #1

样例输入 #1

3
3 7
-1 2
2 3
-3 2
10 472
-4 12
1 29
2 77
-1 86
0 51
3 81
3 17
-2 31
-4 65
4 23
1 1000000000
4 1000000000

样例输出 #1

4
53910
2000000002000000000

提示

数据范围

• $1\ \leq\ T\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $\sum\ N\ \leq\ 2\times\ 10^5$
• $1\ \leq\ M\ \leq\ 10^9$
• $|x_i|\ \leq\ 4\ \,\ (1\ \leq\ i\ \leq\ N)$
• $y_i\ \gt\ 0\ \,\ (1\ \leq\ i\ \leq\ N)$
• $\sum_{k\ =\ 1}^N\ y_k\ =\ M$