AT_pakencamp_2025_day3_q Thorny Path

$ T $ 個のテストケースについて、以下の問題を解いてください。 この森は $ 2 $ 行 $ N $ 列のグリッドとみなすことができます。それぞれのマスには「トゲトゲ度」と呼ばれる正整数が定められており、上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ とすると、そのトゲトゲ度は $ T_{i,j} $ です。 植物を司る神であるけいすけさんは、神力「伐採」を 1 回行うことで次の操作を行うことができます。 - トゲトゲ度が正であるマス $ (a,b) $ （ $ 1 \leq a \leq 2,\ 1 \leq b \leq N $ ）を 1 つ選び、そのマスのトゲトゲ度を $ 1 $ 減らす。ただし、トゲトゲ度を負にすることはできない。 はるくさんは現在マス $ (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 $ 番目のテストケースにおいてけいすけさんが行う必要がある「伐採」の回数の最小値を出力せよ。

### Universal Cup参加者へ この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。 ### Sample Explanation 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 $ になります。 ### Constraints - $ 1 \le T \le 2 \times 10^5 $ - $ 1 \le N \le 2 \times 10^5 $ - $ 1 \le S \le 2 \times 10^{14} $ - $ 1 \le T_{i,j} \le 10^9 $ - 各テストケースの $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力はすべて整数