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

Есеп 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, j)$ ұяшығының iшектi доминентi орын тәртiбiн сақтап $l$-дi $d$ қосылғышқа жiктеудiң әдiстерiне тең. Бұл жердегi $l(i, j)$ сандарының ең үлкенi, ал $d$ ең кiш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 200).$ Келесi $N$ жолдың әрқайсысында $M$ оң, әрқайсысы $10^{18}$ аспайтын сандар берiлген. Соңғы жолда $S$ — бастапқы көңiл күйi берiледi $(1 \le S \le 10^{1000}).$

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

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

Примеры:

Вход

2 3
100 1 10000 
10000 1 1 
100

Ответ

95