Наследство Степана
Степан получил в наследство от деда стоянку на 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.
Выходные данные
Вывести одно число - максимальную прибыль стоянки.