{"raw_statement":[{"iden":"problem statement","content":"There is a grid with $N$ rows and $N$ columns. Let $(i,j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.\nTakahashi is initially at square $(1,1)$ with zero money.\nWhen Takahashi is at square $(i,j)$, he can perform one of the following in one **action**:\n\n*   Stay at the same square and increase his money by $P_{i,j}$.\n*   Pay $R_{i,j}$ from his money and move to square $(i,j+1)$.\n*   Pay $D_{i,j}$ from his money and move to square $(i+1,j)$.\n\nHe cannot make a move that would make his money negative or take him outside the grid.\nIf Takahashi acts optimally, how many actions does he need to reach square $(N,N)$?"},{"iden":"constraints","content":"*   $2 \\leq N \\leq 80$\n*   $1 \\leq P_{i,j} \\leq 10^9$\n*   $1 \\leq R_{i,j},D_{i,j} \\leq 10^9$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$P_{1,1}$ $\\ldots$ $P_{1,N}$\n$\\vdots$ \n$P_{N,1}$ $\\ldots$ $P_{N,N}$\n$R_{1,1}$ $\\ldots$ $R_{1,N-1}$\n$\\vdots$\n$R_{N,1}$ $\\ldots$ $R_{N,N-1}$\n$D_{1,1}$ $\\ldots$ $D_{1,N}$\n$\\vdots$\n$D_{N-1,1}$ $\\ldots$ $D_{N-1,N}$"},{"iden":"sample input 1","content":"3\n1 2 3\n3 1 2\n2 1 1\n1 2\n4 3\n4 2\n1 5 7\n5 3 3"},{"iden":"sample output 1","content":"8\n\n![image](https://img.atcoder.jp/abc344/ec8d878cbf8ad189f178d8b5a3262974.png)\nIt is possible to reach square $(3,3)$ in eight actions as follows:\n\n*   Stay at square $(1,1)$ and increase money by $1$. His money is now $1$.\n*   Pay $1$ money and move to square $(2,1)$. His money is now $0$.\n*   Stay at square $(2,1)$ and increase money by $3$. His money is now $3$.\n*   Stay at square $(2,1)$ and increase money by $3$. His money is now $6$.\n*   Stay at square $(2,1)$ and increase money by $3$. His money is now $9$.\n*   Pay $4$ money and move to square $(2,2)$. His money is now $5$.\n*   Pay $3$ money and move to square $(3,2)$. His money is now $2$.\n*   Pay $2$ money and move to square $(3,3)$. His money is now $0$."},{"iden":"sample input 2","content":"3\n1 1 1\n1 1 1\n1 1 1\n1000000000 1000000000\n1000000000 1000000000\n1000000000 1000000000\n1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000"},{"iden":"sample output 2","content":"4000000004"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}