Problem Description

On the left plate of a balance, there are $ N $ coins stacked vertically, referred to as coin $ 1 $, coin $ 2 $, $\cdots$, coin $ N $ from top to bottom. These coins change mass daily due to oxidation or other factors. The mass of coin $ j $ on day $ i $ is $ M_{i,j} $.

You will play the following game for $ D $ days:

• Move any number of coins from the top of the stack on the left plate to the right plate. You may choose not to move any coins.
• Let $ G $ be the mass of the counterweight needed to balance the scale. $ G $ is the absolute value of the difference in total mass between the coins on the left and right plates.
• You pay a cost of $ G $.

Write a program to find the minimum total cost you need to pay over the $ D $ days.

Input Format

The input is given from the standard input in the following format:

$ N $ $ D $ $ M_{1,1} $ $ M_{1,2} $ $ ... $ $ M_{1,N} $ $ M_{2,1} $ $ M_{2,2} $ $ ... $ $ M_{2,N} $ $\vdots$ $ M_{D,1} $ $ M_{D,2} $ $ ... $ $ M_{D,N} $

Output Format

Output the minimum total cost you need to pay over the $ D $ days on a single line to the standard output.

Sample Input and Output

Sample Input #1

3 4
10 8 3
5 7 8
9 6 1
2 8 9

Sample Output #1

14

Sample Input #2

10 8
50 8 226 426 123 30 114 304 230 994
402 230 316 555 193 95 547 66 171 1000
399 30 24 177 97 325 315 1 361 993
606 973 94 32 391 116 64 782 784 631
759 1000 130 503 81 538 260 41 71 118
1000 148 223 149 113 1 110 366 56 113
1000 245 104 383 171 27 244 34 204 121
55 1000 32 151 59 44 270 386 36 104

Sample Output #2

6733

Sample Input #3

1 10
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000

Sample Output #3

10000000000

Notes/Hints

Constraints

• $1 \leq N \leq 2,000$.
• $1 \leq D \leq 2,000$.
• $1 \leq M_{i,j} \leq 1,000,000,000$ $(1 \leq i \leq D, 1 \leq j \leq N)$.

Subtasks

1. ($ 8 $ points) $ N = 2 $.
2. ($ 8 $ points) $ N = 3 $.
3. ($ 14 $ points) $N \leq 10$, $D \leq 10$.
4. ($ 24 $ points) $N \leq 200$, $D \leq 200$.
5. ($ 46 $ points) No additional constraints.

Sample Explanation 1

By performing the following operations, the total cost paid is $ 14 $, which is the minimum. This input example satisfies the constraints of subtasks $ 2, 3, 4, 5 $.

• On the 1st day, move 1 coin. The cost paid is $ |10 - (8 + 3)| = 1 $.
• On the 2nd day, do not move any coins. The cost paid is $ |5 - (7 + 8)| = 10 $.
• On the 3rd day, do not move any coins. The cost paid is $ |9 - (6 + 1)| = 2 $.
• On the 4th day, move 1 coin. The cost paid is $ |(2 + 8) - 9| = 1 $.

Sample Explanation 2

This input example satisfies the constraints of subtasks $ 3, 4, 5 $.

Sample Explanation 3

This input example satisfies the constraints of subtasks $ 3, 4, 5 $. Note that the output may not fit within a 32-bit integer type.

见题面 Input 部分

见题面 Output 部分