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

Есеп H. Дәлелденген жылан

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

2 секунды

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

256 мегабайта

$N \times M$ тақтасында $(1, 1)$ ұяшығында өз алдына қойған мақсаттарын жүзеге асырғысы және $(N, M)$ ұяшығына мүмкiндiгiнше ең дәлелдi болып барғысы келетiн, жылан тұр. Жылан астыға, оңға және солға жүре алады. Егер жылан $(i, j)$ үяшығына барса, оның көңiл күйi осы ұяшықта жазылған мәнге азаяды.Жыланның ең дәлелдi болып баруы үшiн ол көңiл күйiн ең аз мәнге азайтатын жолды таңдауы тиiс. Сiзге жыланның бастапқы көңiл күйi берiлген. Оның $(N, M)$ ұяшығында болатын ең үлкен болуы мүмкiн көңiл күйiнiң мөлшерiн табыңыз.

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

Енгiзу файлдың бiрiншi жолында екi бүтiн сандар $N$ және $M$ берiледi $(1 \le N,M \le 1000).$ Келесi $N$ жолдың әрқайсысында $M$ оң, әрқайсысы $10^6$-нен аспайтын сандар берiлген. Соңғы жолда $S$ — бастапқы көңiл күйi берiледi $(1 \le S \le 10^{18}).%

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

Бiр санды — есептiң жауабын шығарыңыз.Жауап терiс сан болуы мүмкiн.

Примеры:

Вход

2 2
1 1 
1 1 
100

Ответ

97