{"problem":{"name":"Yakiniku Restaurants","description":{"content":"There are $N$ barbecue restaurants along a street. The restaurants are numbered $1$ through $N$ from west to east, and the distance between restaurant $i$ and restaurant $i+1$ is $A_i$. Joisino has $M","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc067_d"},"statements":[{"statement_type":"Markdown","content":"There are $N$ barbecue restaurants along a street. The restaurants are numbered $1$ through $N$ from west to east, and the distance between restaurant $i$ and restaurant $i+1$ is $A_i$.\nJoisino has $M$ tickets, numbered $1$ through $M$. Every barbecue restaurant offers barbecue meals in exchange for these tickets. Restaurant $i$ offers a meal of _deliciousness_ $B_{i,j}$ in exchange for ticket $j$. Each ticket can only be used once, but any number of tickets can be used at a restaurant.\nJoisino wants to have $M$ barbecue meals by starting from a restaurant of her choice, then repeatedly traveling to another barbecue restaurant and using unused tickets at the restaurant at her current location. Her eventual _happiness_ is calculated by the following formula: \"(The total deliciousness of the meals eaten) - (The total distance traveled)\". Find her maximum possible eventual happiness.\n\n## Constraints\n\n*   All input values are integers.\n*   $2≤N≤5×10^3$\n*   $1≤M≤200$\n*   $1≤A_i≤10^9$\n*   $1≤B_{i,j}≤10^9$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $A_2$ $...$ $A_{N-1}$\n$B_{1,1}$ $B_{1,2}$ $...$ $B_{1,M}$\n$B_{2,1}$ $B_{2,2}$ $...$ $B_{2,M}$\n$:$\n$B_{N,1}$ $B_{N,2}$ $...$ $B_{N,M}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc067_d","tags":[],"sample_group":[["3 4\n1 4\n2 2 5 1\n1 3 3 2\n2 2 5 1","11\n\nThe eventual happiness can be maximized by the following strategy: start from restaurant $1$ and use tickets $1$ and $3$, then move to restaurant $2$ and use tickets $2$ and $4$."],["5 3\n1 2 3 4\n10 1 1\n1 1 1\n1 10 1\n1 1 1\n1 1 10","20"]],"created_at":"2026-03-03 11:01:14"}}