A beacon relay is a grid of R rows and C columns; each cell holds an integer cost (which may be negative). A signal passes through exactly one cell in every row, from row 0 down to row R-1. The only rule linking rows is that the column chosen in a row must differ from the column chosen in the row immediately above it (any other column is allowed, not just adjacent ones).
Determine the minimum possible sum of the chosen cells over all rows.
Input format
Line 1: two integers R and C.
Next R lines: each contains C integers, the costs of that row.
Output format
A single integer: the minimum total cost of choosing one cell per row so that no two consecutive rows share a column.
Constraints
- 1 <= R <= 200
- 2 <= C <= 200
- -1000 <= each cost <= 1000