AT_abc240_f [ABC240F] Sum Sum Max

[problemUrl]: https://atcoder.jp/contests/abc240/tasks/abc240_f 長さ $ M $ の整数列 $ A,\ B,\ C $ があります。 $ C $ は整数 $ x_1,\ \dots,\ x_N,\ y_1,\ \dots,\ y_N $ によって表されます。$ C $ の先頭 $ y_1 $ 項は $ x_1 $ であり、続く $ y_2 $ 項は $ x_2 $ であり、$ \ldots $、末尾の $ y_N $ 項は $ x_N $ です。 $ B $ は $ B_i\ =\ \sum_{k\ =\ 1}^i\ C_k\ \,\ (1\ \leq\ i\ \leq\ M) $ によって定められます。 $ A $ は $ A_i\ =\ \sum_{k\ =\ 1}^i\ B_k\ \,\ (1\ \leq\ i\ \leq\ M) $ によって定められます。 $ A_1,\ \dots,\ A_M $ の最大値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ x_1 $ $ y_1 $ $ \vdots $ $ x_N $ $ y_N $

$ T $ 行出力せよ。$ i\ \,\ (1\ \leq\ i\ \leq\ T) $ 行目には、$ i $ 個目のテストケースに対する答えを出力せよ。

### 制約 - $ 1\ \leq\ T\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1 $ つのファイルに含まれるテストケースについて、$ N $ の総和は $ 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 $ - 入力は全て整数 ### Sample Explanation 1 $ 1 $ つ目のテストケースにおいて、 - $ C\ =\ (-1,\ -1,\ 2,\ 2,\ 2,\ -3,\ -3) $ - $ B\ =\ (-1,\ -2,\ 0,\ 2,\ 4,\ 1,\ -2) $ - $ A\ =\ (-1,\ -3,\ -3,\ -1,\ 3,\ 4,\ 2) $ であるので、$ A_1,\ \dots,\ A_M $ の最大値は $ 4 $ です。