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

Условие

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

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

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

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

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

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

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

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

3 3 2 2

1

Разбор

Давайте раскрасим поле в kd цветов следующим образом:

Несложно заметить, что такой раскраской корабль будет иметь клетки всех kd цветов (вне зависимости от его расположения). Значит, надо найти номер цвета, который встречается реже всего на доске. Несложно заметить, что это цвет под номером kd. Задача свелась к поиску количества клеток, которые покрашены в цвет под номером kd.

Порисовав на листике пару прямоугольников, можно вывести ответ на задачу, который равен ⌊ nk⌋  * ⌊ md⌋.