Власник компанії Megasoft Гілл Бейтс вирішив побудувати хмарочос для нового офісу і замовив проект наймоднішому архітекторові Василеві Чолокаменю. Проект вийшов що треба - прямокутна цегельна будівля n*m футів без єдиного вікна (щоб конкуренти не підглядали). Для економії грошей вирішили, що зовнішні стіни мають бути завтовшки в один фут, а від внутрішніх вирішили відмовитися. Цегла, яку в достатку закупили для будівництва, була двох типів - 1*1*a і 1*1*b футів, та така міцна, що цеглину неможливо розділити на частини. Як з'ясувалося, цеглу можна розташовувати в стіні тільки так, щоб грані 1*1 були вертикальними (тобто "лежачи", шарами). Стіна має бути гладенькою, без отворів і виступів усередині і зовні. Гілл Бейтс відмітив, що шар цегли можна викласти різними способами (а, можливо, і не можна) і вирішив, що в новій будівлі всі можливі способи укладання повинні використовуватися рівно по одному разу для кожного шару цеглин . Чолокамінь з цим погодився, але підрахувати висоту офісу не зміг. Гілл Бейтс теж не зміг, хоча він і програміст. А ви зможете?
Технічні умови. Програма Skyscraper читає з клавіатури в одному рядку 4 розділених пропуском натуральних числа m, n, а, b (3<=m,n<=40, 2<=a,b<=40, a<>b). Програма виводить на екран висоту хмарочоса. Якщо хмарочос з даного комплекту цегли збудувати неможливо, вивести 0.
Приклад.
Введення
10 6 3 4
Виведення
12