Скарби білої кобри#1404

Скарби білої кобри

1 секунда
64 мегабайти
Середня

Поступово перед Мауглі з'явилася кобра — більша, ніж будь-коли він бачив. Ця змія, майже у вісім футів завдовжки, стала білою, наче слонової кістки, від постійної темряви. Навіть кругла мітка на її роздутій шиї зблідла до блідо-жовтого кольору. Очі кобри були червоні, як рубіни, і вся істота здавалася водночас дивною й чудовою.

Ось що сказала біла кобра Мауглі:

— Я — сторож королівського скарбу. Курун Раджа збудував наді мною кам’яну споруду ще тоді, коли моя шкіра була темною, і я могла приносити смерть тим, хто приходить сюди красти. Через каміння вони спускали скарб, і я чула співи брахманів — моїх володарів.

Брахмани спорудили скарбницю у вигляді прямокутника з N \times M квадратних кімнат. Зайшовши у скарбницю, ви опиняєтесь у кімнаті з позначенням S(s_x, s_y) на плані, і вийти на світло можна лише через кімнату F(f_x, f_y). Вам треба знати одну таємницю, яка врятує вас від певної смерті після зустрічі з Туу. У кожній кімнаті лежать Упанішади — давні індійські трактати. Упанішади здебільшого описують безособовий аспект Абсолютної Істини, а також вказують, скільки монет можна взяти з цієї кімнати. У кімнаті можна взяти мішки для зберігання золота. Проходячи через кімнату, ви маєте покласти у мішок рівно стільки золотих монет, скільки вказано в Упанішадах — не більше й не менше. Якщо золото не поміщається до мішка (бо мішок повний), потрібно залишити цей мішок. Вийти з кімнати ви можете лише з одним мішком, і не повинно залишитись порожніх мішків, взятих у кімнаті . Однак може виявитись, що вийти взагалі неможливо...

Вхідні дані

У першому рядку два числа та — розміри скарбниці. У другому рядку — координати кімнати , у третьому — кімнати . У четвертому рядку число — скільки монет вміщається у одному мішку. Далі йдуть рядків по чисел у кожному — це настанови з Упанішад, які вказують, скільки золота можна взяти у кожній кімнаті.

Обмеження: 1 \leq N \leq 100, 1 \leq M \leq 100, 1 \leq K \leq 1000, усі числа з Упанішад від до .

Вихідні дані

Виведіть одне число — скільки мішків треба взяти з кімнати , щоб вийти живим з кімнати . Якщо вийти неможливо, виведіть .

Приклади

Приклад 1

Loading
Loading