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

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

На доске $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