Республиканская олимпиада по информатике, 2011 год, 9 класс

Задача H. Мотивированная змея

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайта

На доске $N \times M$ в клетке $(1, 1)$ находится змея, которая хочет дойти до клетки $(N, M)$ максимально мотивированной для осуществления своих целей. Змея может ходить вниз, вправо и влево. Если змея пойдет в клетку $(i,j),$ то ее настроение уменьшится на величину, написанную на этой клетке. Для того, чтобы дойти максимально мотивированной змея должна выбрать такой путь, при котором ее настроение уменьшится на минимально возможную величину. Вам задано начальное настроение змеи. Найдите максимально возможное настроение, которое будет у нее в клетке $(N, M).$

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

В первой строке входного файла задаются $N$ и $M$ $(1 \le N,M \le 1000).$ В следующих $N$ строках задаются по $M$ положительных целых чисел, каждое из которых не больше чем $10^6$ — числа написанные на клетках. В последней строке задается $S$ — начальное настроение $(1 \le S \le 10^{18}).$

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

Выведите одно число — ответ к задаче. Ответ может быть отрицательным.

Примеры:

Вход

2 2
1 1 
1 1 
100

Ответ

97