AT_abc344_f [ABC344F] Earn to Advance

[problemUrl]: https://atcoder.jp/contests/abc344/tasks/abc344_f 縦 $ N $ 行横 $ N $ 列のグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,j) $ と表します。 高橋君は最初マス $ (1,1) $ におり、所持金は $ 0 $ です。 高橋君はマス $ (i,j) $ にいるとき、$ 1 $ 回の**行動**で以下のいずれかを行うことができます。 - 同じマスにとどまり、所持金を $ P_{i,j} $ 増やす。 - 所持金から $ R_{i,j} $ 払ってマス $ (i,j+1) $ に移動する。 - 所持金から $ D_{i,j} $ 払ってマス $ (i+1,j) $ に移動する。 所持金が負になる移動、グリッドの外に出る移動はできません。 高橋君が最適に行動したとき、何回の行動でマス $ (N,N) $ にたどり着くことができますか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_{1,1} $ $ \ldots $ $ P_{1,N} $ $ \vdots $ $ P_{N,1} $ $ \ldots $ $ P_{N,N} $ $ R_{1,1} $ $ \ldots $ $ R_{1,N-1} $ $ \vdots $ $ R_{N,1} $ $ \ldots $ $ R_{N,N-1} $ $ D_{1,1} $ $ \ldots $ $ D_{1,N} $ $ \vdots $ $ D_{N-1,1} $ $ \ldots $ $ D_{N-1,N} $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 80 $ - $ 1\ \leq\ P_{i,j}\ \leq\ 10^9 $ - $ 1\ \leq\ R_{i,j},D_{i,j}\ \leq\ 10^9 $ - 入力は全て整数である ### Sample Explanation 1 !\[図\](https://img.atcoder.jp/abc344/ec8d878cbf8ad189f178d8b5a3262974.png) 以下のようにして $ 8 $ 回の行動でマス $ (3,3) $ にたどり着くことができます。 - マス $ (1,1) $ にとどまり、所持金を $ 1 $ 増やす。所持金は $ 1 $ になる。 - 所持金から $ 1 $ 払ってマス $ (2,1) $ に移動する。所持金は $ 0 $ になる。 - マス $ (2,1) $ にとどまり、所持金を $ 3 $ 増やす。所持金は $ 3 $ になる。 - マス $ (2,1) $ にとどまり、所持金を $ 3 $ 増やす。所持金は $ 6 $ になる。 - マス $ (2,1) $ にとどまり、所持金を $ 3 $ 増やす。所持金は $ 9 $ になる。 - 所持金から $ 4 $ 払ってマス $ (2,2) $ に移動する。所持金は $ 5 $ になる。 - 所持金から $ 3 $ 払ってマス $ (3,2) $ に移動する。所持金は $ 2 $ になる。 - 所持金から $ 2 $ 払ってマス $ (3,3) $ に移動する。所持金は $ 0 $ になる。