Скарби білої кобри
Мало-помалу перед Мауглі піднялася така велика кобра, яких він ще ніколи не бачив. Це була змія майже у вісім футів довжини, яка от постійного перебування в темноті побіліла, як слонова кістка. Навіть круглий знак на її раздутоі шиї став блідно-жовтим. Очі білої кобри були красні, як смарагди, і вся вона здавалася дивною і дивовижною.
Ось що розповіла біла кобра Мауглі.
– Я – охоронець королівського скарбу. Куррун Раджа збудував наді мною кам'яну будівлю в ті дні, коли шкіра моя була темна, і я міг приносити смерть тим хто приходив сюда для крадіжки. Крізь каміння опустили скарб, і я чув спів брамінів, моїх повелителів.
Браміни збудувалили сховтще у вигляді прямокутника NxM з квадратних кімнат. Потрапивши у сховище, ви опиняєтесь в одній з кімнат, яка на плані позначена S(sx,sy), а вийти на світло можна лише через кімнату F(fx,fy). При цьому потрібно знати одну таємницю, яка вбереже вас від вірної загибелі після зустрічі з Туу. У кожній кімнаті є Упанішади – трактати стародавньої Індії. В Упанішадах головним чином описується безособистий аспект Абсолютної Істини, а також є вказівка, скільки монет можна винести з цієї кімнати. У кімнаті S можна взяти сумки, у які буде складатись золото. При проході через якусь кімнату, у сумку потрібно покласти рівно стілько золотих монет, скільки вказано в Упанішадах – ні більше, ні менше. Якщо покласти золото у сумку не можна (сумка переповнюється), тоді цю сумку потрібно залишити. З кімнати F можна вийти лише з однією сумкою і пустих сумок, взятих у кімнаті S не повинно залишитись. Проте, можна і не выйти…
Вхідні дані
У першому рядку вхідного файлу записано числа N і M (розміри сховища), у 2-му рядку – координати кімнати S, у 3-му рядку – координати кімнати F, у 4-му рядку – число K (кількість монет, що поміщуються в одній сумці). Далі йде N рядків по M чисел – вказівки з Упанішад, скільки золота можна взяти у відповідній кімнаті.
Обмеження: 1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ K ≤ 1000, всі числа з Упанішад – від 1 до 1000.
Вихідні дані
У вихідний файл слід вивести одне число – кількість сумок, які необхідно взяти у кімнаті S, щоб живим вийти з кімнати F. Якщо вийти не вдасться – вивести -1.