Garage
Garage
Вау! Какой счастливый день! Ваша компания только что выиграла социальный контракт для строительства гаражного комплекса. Почти все формальности соблюдены: оплата контракта уже переведена на Ваш счет.
So now it is the right time to read the contract. Okay, there is a sandlot in the form of W × H rectangle and you have to place some garages there. Garages are w × h rectangles and their edges must be parallel to the corresponding edges of the sandlot (you may not rotate garages, even by 90°). The coordinates of garages may be non-integer.
You know that the economy must be economical, so you decided to place as few garages as possible. Unfortunately, there is an opposite requirement in the contract: placing maximum possible number of garages.
Now let's see how these requirements are checked... The plan is accepted if it is impossible to add a new garage without moving the other garages (the new garage must also have edges parallel to corresponding sandlot edges).
Accepted optimal plan Rejected plan Accepted, but non-optimal plan
Time is money, find the minimal number of garages that must be ordered, so that you can place them on the sandlot and there is no place for an extra garage.
Входные данные
В одной строке содержатся четыре числа: W, H, w, h - размеры участка и размеры гаража в метрах. Считайте, что 1 ≤ w ≤ W ≤ 30000 и 1 ≤ h ≤ H ≤ 30000.
Выходные данные
Выведите оптимальное количество гаражей.
11 4 3 2
2
10 8 3 4
2
15 7 4 2
4