{"problem":{"name":"Sum Sum Max","description":{"content":"There are integer sequences $A, B, C$ of length $M$ each. $C$ is represented by integers $x_1, \\dots, x_N, y_1, \\dots, y_N$. The first $y_1$ terms of $C$ are $x_1$, the subsequent $y_2$ terms are $x_2","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc240_f"},"statements":[{"statement_type":"Markdown","content":"There are integer sequences $A, B, C$ of length $M$ each.\n$C$ is represented by integers $x_1, \\dots, x_N, y_1, \\dots, y_N$. The first $y_1$ terms of $C$ are $x_1$, the subsequent $y_2$ terms are $x_2$, $\\ldots$, the last $y_N$ terms are $x_N$.\n$B$ is defined by $B_i = \\sum_{k = 1}^i C_k \\, (1 \\leq i \\leq M)$.\n$A$ is defined by $A_i = \\sum_{k = 1}^i B_k \\, (1 \\leq i \\leq M)$.\nFind the maximum value among $A_1, \\dots, A_M$.\nYou will be given $T$ test cases to solve.\n\n## Constraints\n\n*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   The sum of $N$ in a single file is at most $2 \\times 10^5$.\n*   $1 \\leq M \\leq 10^9$\n*   $|x_i| \\leq 4 \\, (1 \\leq i \\leq N)$\n*   $y_i \\gt 0 \\, (1 \\leq i \\leq N)$\n*   $\\sum_{k = 1}^N y_k = M$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is in the following format:\n\n$N$ $M$\n$x_1$ $y_1$\n$\\vdots$\n$x_N$ $y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc240_f","tags":[],"sample_group":[["3\n3 7\n-1 2\n2 3\n-3 2\n10 472\n-4 12\n1 29\n2 77\n-1 86\n0 51\n3 81\n3 17\n-2 31\n-4 65\n4 23\n1 1000000000\n4 1000000000","4\n53910\n2000000002000000000\n\nIn the first test case, we have:\n\n*   $C = (-1, -1, 2, 2, 2, -3, -3)$\n*   $B = (-1, -2, 0, 2, 4, 1, -2)$\n*   $A = (-1, -3, -3, -1, 3, 4, 2)$\n\nThus, the maximum value among $A_1, \\dots, A_M$ is $4$."]],"created_at":"2026-03-03 11:01:13"}}