| Автор: | Женя Татаринов, Бадерик П.М. | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход |
Женя с Анжеликой играют в морской бой! Поле Анжелики представлено в виде клетчатого прямоугольника из n строк и m столбцов. На поле находится один единственный корабль, который представлен в виде клетчатого прямоугольника из k строк и d столбцов (обратите внимание, что корабль именно таких размеров, его нельзя поворачивать, то есть не может быть корабля из d строк и k столбцов).
Так как Анжелика как всегда победила Женю, Женя решил хотя бы подбить корабль, то есть назвать такую клетку, которая лежит внутри корабля. Анжелика же хочет, чтобы Женя не смог подбить корабль, поэтому она позволит Жене сделать такое количество выстрелов q, которое является минимальным количеством выстрелов, для которого существует стратегия выстрелов, следуя которой можно подбить корабль вне зависимости от его местоположения на поле игры.
Какое количество выстрелов Анжелика разрешит сделать Жене?
В первой строке входных данных вводятся числа n, m, k, d — размеры поля и размеры корабля соответственно (1 ≤ k ≤ n ≤ 109, 1 ≤ d ≤ m ≤ 109).
Выведите ответ на задачу.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|