AT_pakencamp_2025_day3_q Thorny Path

请针对 $T$ 个测试用例，解决以下问题。 这片森林可以被看作是 $2$ 行 $N$ 列的网格。每个格子都有一个称为“刺刺度”的正整数，对于自上而下第 $i$ 行、自左而右第 $j$ 列的格子 $(i,j)$，其刺刺度为 $T_{i,j}$。 作为掌管植物的神，けいすけ先生每进行一次神力“伐采”操作，可以执行下述操作： - 选择任意刺刺度大于 $0$ 的格子 $(a,b)$（$1\leq a \leq 2,\ 1\leq b \leq N$），使该格子的刺刺度减少 $1$。但刺刺度不能减为负数。 现在，はるく先生位于格子 $(1,1)$，并希望只通过向右或向下移动，相邻格子之间依次跳跃，最终到达格子 $(2,N)$。 你需要帮けいすけ先生事先适当地进行若干次“伐采”（可以对格子的刺刺度减到 $0$），使得无论はるく先生选择哪一条从 $(1,1)$ 到 $(2,N)$ 的路径，他所经过的所有格子（包括 $(1,1)$ 和 $(2,N)$）上的刺刺度总和都不超过 $S$。 请计算满足上述条件所需的最小“伐采”操作次数。

输入从标准输入读取。第 $1$ 行输入为： > $T$ 接下来有 $T$ 个测试用例。每个测试用例包含以下格式： > $N\ S\ T_{1,1}\ T_{1,2}\ \ldots\ T_{1,N}\ T_{2,1}\ T_{2,2}\ \ldots\ T_{2,N}$

输出共 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例为使“はるく先生所有路径所经格子刺刺度之和均 $\leq S$” 所需的最小“伐采”操作次数。

### 致 Universal Cup 参赛者 此题在 Universal Cup 中将被移除。因此，如果你在 AtCoder 上使用 Universal Cup 结果，请先做除本题外的其他题目。 ### 样例解释 1 这个输入包含 $3$ 个测试用例。 对于第 $1$ 个测试用例，初始状态如下： ``` 1 2 3 4 5 6 ``` けいすけ先生通过如下 $13$ 次“伐采”操作，可以把森林的刺刺度变为： ``` 0 1 3 4 0 0 ``` - 对格子 $(1,1)$ 操作 $1$ 次 - 对格子 $(1,2)$ 操作 $1$ 次 - 对格子 $(2,2)$ 操作 $5$ 次 - 对格子 $(2,3)$ 操作 $6$ 次 此时，无论从 $(1,1)$ 移动到 $(2,3)$ 的路径怎么选，所经过所有格子的刺刺度之和都不会超过 $4$，满足题意。 用 $12$ 次或更少的伐采无法达成，所以答案是 $13$。 ### 数据范围 - $1\leq T\leq 2\times 10^5$ - $1\leq N\leq 2\times 10^5$ - $1\leq S\leq 2\times 10^{14}$ - $1\leq T_{i,j}\leq 10^9$ - 所有测试用例中 $N$ 的总和不超过 $2\times 10^5$ - 输入均为整数 由 ChatGPT 5 翻译