Clear the Game

Interview

Time limit1sMemory limit512 MB

Summary

Pick one weapon per run so that consecutive runs never share a weapon, minimizing the total clear time over N runs.

Level: Medium4 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

Sanjini plays the game Elden Ring. The game has so much to do that replaying from the start, called a run, is popular. After one clear, a player has finished run 1, and after two clears, run 2. At the start of each run, a player can freely choose any weapon to begin with, such as a dagger, straight sword, curved sword, or magic. Sanjini has a strong pride and never switches weapons in the middle of a run, clearing it to the end. Sanjini plans to play several runs and, to make the game more fun, decides not to use the weapon from the immediately previous run. The game randomly adjusts stats whenever a new run starts, so the efficient weapon changes from run to run. Sanjini wants to clear the game as efficiently as possible. If Sanjini picks the best weapons, how fast can the game be finished?

Input

The first line has two integers N and M, separated by a space. N is the number of runs Sanjini plays, and M is the number of weapon types. ( $2 \le N, M \le 500$ )

From the second line, each of the N lines gives the clear times $t_1, t_2, \cdots, t_M$ for each weapon, separated by spaces. ( $1 \le t_i \le 10\,000$ )

All numbers in the input are integers.

Output

Print the minimum total clear time when the most efficient weapon is picked for every run.

Examples2

Example 1
Input
```
2 2
3 2
1 4
```
Expected output
```
3
```

Example 2

Input

5 5
1 10 10 10 10
10 10 1 10 10
10 1 10 10 10
10 10 10 1 10
10 10 10 10 1

Expected output