Задача F. Морской бой

Автор:Женя Татаринов, Бадерик П.М.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Женя с Анжеликой играют в морской бой! Поле Анжелики представлено в виде клетчатого прямоугольника из n строк и m столбцов. На поле находится один единственный корабль, который представлен в виде клетчатого прямоугольника из k строк и d столбцов (обратите внимание, что корабль именно таких размеров, его нельзя поворачивать, то есть не может быть корабля из d строк и k столбцов).

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

Какое количество выстрелов Анжелика разрешит сделать Жене?

Формат входных данных

В первой строке входных данных вводятся числа n, m, k, d  — размеры поля и размеры корабля соответственно (1 ≤ k ≤ n ≤ 109, 1 ≤ d ≤ m ≤ 109).

Формат выходных данных

Выведите ответ на задачу.

Примеры тестов

Стандартный вход Стандартный выход
1
3 3 2 2
1

0.105s 0.012s 13