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

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

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

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

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

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

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

Примеры

Вход

2 3
100 1 10000 
10000 1 1 
100

Выход

95