{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   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$"},{"iden":"input","content":"The 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}$"},{"iden":"sample input 1","content":"3 4\n1 4\n2 2 5 1\n1 3 3 2\n2 2 5 1"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"5 3\n1 2 3 4\n10 1 1\n1 1 1\n1 10 1\n1 1 1\n1 1 10"},{"iden":"sample output 2","content":"20"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}