Республиканская олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

Задача D. Витя - черепашка ниндзя 2

Дается прямоугольная таблица $N × M$, в каждой клетке записано какое-то число. Витя находится в левой верхней клетке, его цель добраться до правого нижнего угла. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). За посещение клетки, Витя должен платить число указанное в этой клетке.

Дончик владелец таблицы. Он решил сделать скидку своему другу Вите, разрешив платить только за самые дорогие(наибольшие по значению) $K$ клеток на его пути от левого верхнего угла в правый нижний.

Какое минимальное количество денег потратит Витя для достижения своей цели?

Формат входного файла

В первой строке даны три целых числа $N, M$ и $K$ $(1 \leq N, M \leq 500, 1 \leq K \leq N + M − 1)$.

В следующих $N$ строках даны по $M$ целых чисел — $j$-е число на $i$-й строке $a_{i,j} (0 \leq a_{i,j} \leq 500)$ является числом на клетке в $i$-й строке и $j$-м столбце таблицы.

Формат выходного файла

Выведите одно целое число — ответ на задачу

Система оценки

Примеры

Ввод

3 3 5
1 1 1
6 6 10
1 7 3

Вывод

16

Ввод

4 4 2
1 3 2 6
7 4 5 2
1 4 6 7
1 0 1 0

Вывод

8