A - Error Analysis of Temperature Forecasts Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は気象予報士を目指しており、 N 地点の気温を毎日予報する練習をしています。

高橋君は D 日間にわたって各地点の気温を予報し、その結果を記録しました。高橋君はまだ練習を始めたばかりなので、地点 i に対する予報気温は毎日同じ値 T_i 度（摂氏）です。一方、 j 日目の地点 i の実際の気温は A_{i,j} 度でした。

地点 i の j 日目における「予報誤差」は、予報気温と実際の気温の差の絶対値 |A_{i,j} - T_i| で定義されます。

高橋君は自分の予報の精度を振り返るため、各地点について D 日間の予報誤差の合計を求めることにしました。具体的には、各地点 i （ 1 \leq i \leq N ）について予報誤差の合計

S_i = \sum_{j=1}^{D} |A_{i,j} - T_i|

を計算します。

S_1, S_2, \ldots, S_N の最大値を求めてください。

制約

  • 1 \leq N \leq 10000
  • 1 \leq D \leq 10000
  • N \times D \leq 10^6
  • -50 \leq T_i \leq 50 （ 1 \leq i \leq N ）
  • -50 \leq A_{i,j} \leq 50 （ 1 \leq i \leq N, 1 \leq j \leq D ）
  • 入力はすべて整数である

入力

N D
T_1 T_2 \ldots T_N
A_{1,1} A_{1,2} \ldots A_{1,D}
A_{2,1} A_{2,2} \ldots A_{2,D}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,D}
  • 1 行目には、地点の数 N と日数 D が、スペース区切りで与えられる。
  • 2 行目には、各地点の予報気温 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
  • 3 行目から N + 2 行目には、各地点の実際の気温が与えられる。
  • 2 + i 行目（ 1 \leq i \leq N ）には、地点 i の D 日間の実際の気温 A_{i,1}, A_{i,2}, \ldots, A_{i,D} が、スペース区切りで与えられる。

出力

S_1, S_2, \ldots, S_N の最大値を整数で 1 行に出力してください。

入力例 1

3 4
10 0 -5
12 8 10 15
0 -3 4 1
-10 -5 0 -4

出力例 1

11

入力例 2

2 3
-2 7
-2 -1 -3
10 7 4

出力例 2

6

入力例 3

6 8
-10 0 15 20 -25 5
-10 -8 -12 0 10 -20 -30 -10
0 1 -1 2 -2 3 -3 4
15 15 16 14 30 0 -15 50
20 19 18 21 22 23 24 25
-50 -40 -30 -25 -20 -10 0 10
5 -5 15 -15 25 -25 35 -35

出力例 3

160

入力例 4

12 12
-50 -40 -30 -20 -10 0 10 20 30 40 50 5
-50 -49 -48 -47 -46 -45 -44 -43 -42 -41 -40 -39
-50 -45 -40 -35 -30 -25 -20 -15 -10 -5 0 5
-30 -30 -30 -30 -20 -10 0 10 20 30 40 50
-20 -25 -15 -30 -10 -35 -5 -40 0 -45 5 -50
-10 0 -20 10 -30 20 -40 30 -50 40 50 -10
0 0 0 0 0 0 0 0 0 0 0 0
10 9 8 7 6 5 4 3 2 1 0 -1
20 25 30 35 40 45 50 15 10 5 0 -5
30 20 10 0 -10 -20 -30 -40 -50 40 50 30
40 41 42 43 44 45 46 47 48 49 50 39
-50 -40 -30 -20 -10 0 10 20 30 40 50 50
5 -5 15 -15 25 -25 35 -35 45 -45 50 -50

出力例 4

550

入力例 5

1 1
-50
50

出力例 5

100

Score : 233 pts

Problem Statement

Takahashi aims to become a weather forecaster and is practicing by forecasting the daily temperature at N locations.

Takahashi forecasted the temperature at each location over D days and recorded the results. Since he has just started practicing, his forecasted temperature for location i is the same value T_i degrees (Celsius) every day. On the other hand, the actual temperature at location i on day j was A_{i,j} degrees.

The "forecast error" for location i on day j is defined as the absolute difference between the forecasted temperature and the actual temperature, |A_{i,j} - T_i|.

To review the accuracy of his forecasts, Takahashi decided to find the sum of the forecast errors over the D days for each location. Specifically, for each location i (1 \leq i \leq N), he calculates the total forecast error:

S_i = \sum_{j=1}^{D} |A_{i,j} - T_i|

Find the maximum value among S_1, S_2, \ldots, S_N.

Constraints

  • 1 \leq N \leq 10000
  • 1 \leq D \leq 10000
  • N \times D \leq 10^6
  • -50 \leq T_i \leq 50 (1 \leq i \leq N)
  • -50 \leq A_{i,j} \leq 50 (1 \leq i \leq N, 1 \leq j \leq D)
  • All input values are integers.

Input

N D
T_1 T_2 \ldots T_N
A_{1,1} A_{1,2} \ldots A_{1,D}
A_{2,1} A_{2,2} \ldots A_{2,D}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,D}
  • The first line contains the number of locations N and the number of days D, separated by a space.
  • The second line contains the forecasted temperatures for each location, T_1, T_2, \ldots, T_N, separated by spaces.
  • The third to (N + 2)-th lines contain the actual temperatures for each location.
  • The (2 + i)-th line (1 \leq i \leq N) contains the actual temperatures at location i over the D days, A_{i,1}, A_{i,2}, \ldots, A_{i,D}, separated by spaces.

Output

Print the maximum value among S_1, S_2, \ldots, S_N as an integer in a single line.

Sample Input 1

3 4
10 0 -5
12 8 10 15
0 -3 4 1
-10 -5 0 -4

Sample Output 1

11

Sample Input 2

2 3
-2 7
-2 -1 -3
10 7 4

Sample Output 2

6

Sample Input 3

6 8
-10 0 15 20 -25 5
-10 -8 -12 0 10 -20 -30 -10
0 1 -1 2 -2 3 -3 4
15 15 16 14 30 0 -15 50
20 19 18 21 22 23 24 25
-50 -40 -30 -25 -20 -10 0 10
5 -5 15 -15 25 -25 35 -35

Sample Output 3

160

Sample Input 4

12 12
-50 -40 -30 -20 -10 0 10 20 30 40 50 5
-50 -49 -48 -47 -46 -45 -44 -43 -42 -41 -40 -39
-50 -45 -40 -35 -30 -25 -20 -15 -10 -5 0 5
-30 -30 -30 -30 -20 -10 0 10 20 30 40 50
-20 -25 -15 -30 -10 -35 -5 -40 0 -45 5 -50
-10 0 -20 10 -30 20 -40 30 -50 40 50 -10
0 0 0 0 0 0 0 0 0 0 0 0
10 9 8 7 6 5 4 3 2 1 0 -1
20 25 30 35 40 45 50 15 10 5 0 -5
30 20 10 0 -10 -20 -30 -40 -50 40 50 30
40 41 42 43 44 45 46 47 48 49 50 39
-50 -40 -30 -20 -10 0 10 20 30 40 50 50
5 -5 15 -15 25 -25 35 -35 45 -45 50 -50

Sample Output 4

550

Sample Input 5

1 1
-50
50

Sample Output 5

100