/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1000 点
問題文
1 から N までの番号のついた N 軒の焼肉店があります。 焼肉店は番号順に一直線上に並んでいて、i 番目の焼肉店と i+1 番目の焼肉店の距離は A_i です。
joisinoお姉ちゃんは、1 から M までの番号のついた M 枚のチケットを持っています。 どの焼肉店でも、これらのチケットと引き換えに焼き肉を食べられます。 i 番目の焼肉店で、j 番目のチケットと引き換えに食べられる焼き肉の美味しさは B_{i,j} です。 一度使ったチケットは 2 度以上使えません。 また、同じ焼肉店で使うチケットの数に制限はありません。
joisinoお姉ちゃんは、適当な焼肉店の前からスタートして、別の焼肉店の場所へ移動したり、 目の前にある焼肉店でまだ使っていないチケットを使って焼き肉を食べたりすることを繰り返して、M 枚の焼き肉を食べようとしています。 joisinoお姉ちゃんの最終的な幸福度は、「食べた焼き肉の美味しさの総和 - 移動した距離の合計」で求められます。 joisinoお姉ちゃんの最終的な幸福度の最大値を求めてください。
制約
- 入力は全て整数である
- 2≦N≦5×10^3
- 1≦M≦200
- 1≦A_i≦10^9
- 1≦B_{i,j}≦10^9
入力
入力は以下の形式で標準入力から与えられる。
N M
A_1 A_2 ... A_{N-1}
B_{1,1} B_{1,2} ... B_{1,M}
B_{2,1} B_{2,2} ... B_{2,M}
:
B_{N,1} B_{N,2} ... B_{N,M}
出力
joisinoお姉ちゃんの最終的な幸福度の最大値を出力せよ。
入力例 1
3 4 1 4 2 2 5 1 1 3 3 2 2 2 5 1
出力例 1
11
1 番目の焼肉店の前からスタートし、1 番目と 3 番目のチケットを使って焼き肉を食べたあと、 2 番目の焼肉店の前まで移動して、2 番目と 4 番目のチケットを使って焼き肉を食べると、幸福度を最大化できます。
入力例 2
5 3 1 2 3 4 10 1 1 1 1 1 1 10 1 1 1 1 1 1 10
出力例 2
20
Score : 1000 points
Problem Statement
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 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.
Joisino 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.
Constraints
- All input values are integers.
- 2≤N≤5×10^3
- 1≤M≤200
- 1≤A_i≤10^9
- 1≤B_{i,j}≤10^9
Input
The input is given from Standard Input in the following format:
N M
A_1 A_2 ... A_{N-1}
B_{1,1} B_{1,2} ... B_{1,M}
B_{2,1} B_{2,2} ... B_{2,M}
:
B_{N,1} B_{N,2} ... B_{N,M}
Output
Print Joisino's maximum possible eventual happiness.
Sample Input 1
3 4 1 4 2 2 5 1 1 3 3 2 2 2 5 1
Sample Output 1
11
The 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.
Sample Input 2
5 3 1 2 3 4 10 1 1 1 1 1 1 10 1 1 1 1 1 1 10
Sample Output 2
20