29146번 - Морская баталия 다국어

Разведка доложила, что подводная лодка Октавия Спрута находится недалеко от пингвинов. Шкипер без колебаний предложил доесть суши и потопить ее.

Разведкой были добыты данные описания области, в которой находится подлодка. Область представляет из себя прямоугольник $n \times m$. Также удалось выяснить, что подлодка представляет из себя прямоугольник $1 \times k$. Пингвины стали думать, как же им обнаружить судно, как вдруг Прапор случайно нажал на кнопку выстрела, и ракета угодила прямо в какой-то сегмент подлодки. Здесь и дальше под сегментом подлодки будем понимать одну из клеток, которые она занимает. Ковальски посчитал, что теперь вероятность ее потопить составляет все сто процентов. Лодка считается потопленной, если был произведен выстрел в каждый ее сегмент. Для каждого выстрела известно, попал ли он в цель.

Так как теперь одной задачей у Пингвинов стало меньше, они хотят посчитать минимальное количество выстрелов, которые им придется совершить, чтобы гарантированно потопить подводную лодку Октавия (выстрел Прапора уже совершен и в расчет не берется). А поскольку сейчас у них перерыв на сырные хрумки, эту важную задачу они поручают Вам.

В первой строке входного файла содержатся два целых числа $n, m$ ($1 \le n, m \le 20$) --- длина и ширина области, в которой находится подлодка.

Во второй строке входного файла содержатся два целых числа $x, y$ ($1 \le x \le n, 1 \le y \le m$) --- координаты точки, в которую был произведен выстрел.

В третьей строке входного файла дано одно целое число $k$ ($1 \le k \le \max(n, m)$) --- длина подводной лодки.

В единственной строке выходного файла выведите одно целое число --- количество выстрелов, которое Пингвинам придется совершить в худшем случае, чтобы потопить подлодку, если они будут действовать оптимально.

На рисунках приведены примеры расположения подлодок для тестов из условия. Крестиками обозначены фрагменты лодки, точками --- клетки, в которые были могли быть проведены выстрелы, но не было попадания. Окружностью обозначена клетка, в которую был произведен выстрел Прапора.

В первом тестовом примере поражена одна из клеток корабля, а вторая может находиться на любой из соседних, и в худшем случае пингвинам придется сделать четыре выстрела, чтобы добить корабль.

Во втором тестовом примере пингвины могут уничтожить корабль за четыре выстрела. Для этого они могут сначала выстрелить, например, в клетку (2, 3), и понять, как расположен корабль: если он расположен вертикально, то он точно проходит через эту клетку, и они гарантированно уничтожат его еще за два выстрела, а иначе, он расположен горизонтально, и им потребуется еще три выстрела чтобы гарантированно подбить корабль.

В третьем тестовом примере возможно всего одно расположение корабля, и пингвины уничтожают его за три выстрела.