{"problem":{"name":"Earn to Advance","description":{"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. Takahashi is initially at square $(1,1)$ with zero money.","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc344_f"},"statements":[{"statement_type":"Markdown","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)$?\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc344_f","tags":[],"sample_group":[["3\n1 2 3\n3 1 2\n2 1 1\n1 2\n4 3\n4 2\n1 5 7\n5 3 3","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$."],["3\n1 1 1\n1 1 1\n1 1 1\n1000000000 1000000000\n1000000000 1000000000\n1000000000 1000000000\n1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000","4000000004"]],"created_at":"2026-03-03 11:01:14"}}