1921. Стоянка

В районе "Тастак" есть стоянка из `N` мест, пронумерованных от 1 до `N`, и первые `M` мест находятся в левом краю, а остальные `N-M` мест в правом краю.

Каждый день `N` жителей этого района паркуют свои машины на этой стоянке, и известно, что первый житель приходит раньше всех, потом второй, и так далее, то есть `k`-й приходит `k`-м. Также для каждого жителя `i` известно, сколько он будет платить, если его машину поставят на `j`-е место.

На стоянке есть распределитель мест, который каждой приезжающей машине указывает, на какой край парковаться, после чего машина паркуется на минимальное по номеру свободное место соответствующего края. Но так как этот распределитель работает не оптимально, владелец стоянки попросил Вас написать программу для этого распределителя, которая максимизирует прибыль стоянки.

В первой строке находятся два целых числа `N` (`2\ ≤\ N\ ≤\ 1000`) и `M` (`1\ ≤\ M\ <\ N`) — общее количество мест на стоянке и количество мест в левом краю соответственно.

В каждой из следующих `N` строк находятся по `N` целых положительных чисел. `j`-ое число `i`-ой строки обозначает, сколько будет платить `i`-й житель за место с номером `j` на этой стоянке. Каждое из этих чисел не превышает `10^6`.

Выведите одно целое число — максимальную прибыль стоянки.

2 1
3 2
6 4

8

4 1
4 3 1 1
3 1 1 1
1 1 4 1
1 1 1 2

12