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

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

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

2 секунды

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

256 мегабайта

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