eolymp
bolt
Try our new interface for solving problems
Məsələlər

Наследство Степана

Наследство Степана

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Степан получил в наследство от деда стоянку на n мест, пронумерованных от 1 до n. Стоянка разбита на две части. Первые m мест находятся с левой стороны, а другие n - m мест с правой. Каждый день n жителей этого района паркуют свои автомобили на стоянке Степана. Известно, что первый житель приходит раньше всех, потом второй, и так далее, то есть k-ый приходит k-ым. Также для каждого i-го жителя известно, сколько он будет платить, если его машину поставят на j-ое место. Степан приобрёл распределитель мест, котрый каждому приезжаюзему автомобилю показывает, с какой стороны парковаться, после чего автомобиль паркуется на минимальное по номеру свободное место соответствующей стороны. При этом Степан решил сэкономить и не приобрёл программное обеспечение для распределителя, поэтому он работает не оптимально.

Степан просит Вас написать программу для этого распределителя, которая максимизирует прибыль Степана.

Giriş verilənləri

В первой строке записаны два целых числа n (2n1000) и m (1m < n) - общее количество мест на стоянке и количество мест с левой стороны соответственно. В каждой из последующих n строк записано по n целых положительных чисел. j-ое число i-ой строки обозначает, сколько будет платить i-ый житель за место с номером j на этой стоянке. Каждое из этих чисел не превышает 10^6.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2 1
3 2
6 4
Çıxış verilənləri #1
8
Giriş verilənləri #2
4 1
4 3 1 1
3 1 1 1
1 1 4 1
1 1 1 2
Çıxış verilənləri #2
12
Mənbə III этап Всеукраинской олимпиады школьников 2012-2013, 1 тур