ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1498. Удар с разбега

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Вероятно, многие из вас слышали о пошаговой стратегии Losers-V от компании Lavin Interactive. Если вы неравнодушны к этой игре, вы просто обязаны помочь рыцарю, который попал в трудное положение…
Итак, во время сражения рыцарь заметил на горизонте рогатого демона. Несомненно, необходимо нанести удар. Казалось бы, чего проще, скачи и руби! Но рыцарь — особый персонаж: сила его удара зависит от разбега, а длина разбега небезгранична. Помогите же ему решить эту хитрую тактическую задачу.
Поле битвы представляет собой прямоугольник N × M клеток. В начале хода рыцарь стоит на клетке с координатами (x1y1), а рогатый демон — на клетке (x2y2). За один шаг рыцарь может перейти из клетки, где он находится, в одну из смежных по стороне клеток. Всего рыцарь может сделать не более L шагов. Во время разбега не разрешается покидать пределов поля битвы (это будет дезертирством) и заходить на клетку с рогатым демоном. После разбега рыцарь может ударить по демону, если находится в одной из смежных с ним по стороне клеток (удар не считается шагом). Сила удара равняется K + 1, где K — длина прямого участка, который проскакал рыцарь непосредственно перед ударом. Бить разрешается только один раз. Рыцарь очень просит вас сказать, какой максимальный урон он может нанести рогатому демону. Будем считать, что урон равен силе удара.

Исходные данные

Первая строка содержит 3 целых числа: N, M, L (1 ≤ NM ≤ 100; 1 ≤ L ≤ 1000). Во второй строке записаны координаты рыцаря (x1y1). В третьей — координаты рогатого демона (x2y2). (1 ≤ x1x2 ≤ N; 1 ≤ y1y2 ≤ M). Координаты рыцаря и координаты рогатого демона различны.

Результат

Выведите единственное число — максимальный урон, который может причинить рыцарь демону.

Пример

исходные данныерезультат
3 4 4
1 1
3 4
4

Замечания

Рыцарь сдвигается в точку (2, 1), затем в (2, 4) и бьёт. Длина разбега равна 3, соответственно сила удара — 4.
Автор задачи: Алексей Самсонов
Источник задачи: XIII командный чемпионат школьников Свердловской области по программированию (14 октября 2006 года)