3-й этап Республиканской олимпиады по информатике 2022-2023, 2й тур

Задача D. Две очереди

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Есть две очереди. В первой стоят $n$ людей, во второй стоят $m$ людей. В первой очереди обслуживают одного человека за $A$ минут, во второй очереди обслуживают одного человека за $B$ минут. Отсчет времени начинается с минуты $1$. Каждую минуту последовательно происходит следующее:

1. Если первый человек в первой очереди обслужен, то он уходит из очереди.
2. Если первый человек во второй очереди обслужен, то он уходит из очереди.
3. Последний человек в первой очереди перемещается в конец второй очереди если его порядковый номер во второй очереди окажется меньше чем его номер в первой очереди.
4. Последний человек во второй очереди перемещается в конец первой очереди если его порядковый номер в первой очереди окажется меньше чем его номер во второй очереди.

Сообщите первый момент времени $T$ когда все люди будут обслужены.

Формат входного файла

В первой и единственной строке входного файла даны четыре целых числа $n$, $m$, $A$ и $B$ ($1 <= n, m, A, B <= 10^5$).

Формат выходного файла

Выведите одно целое число — первый момент времени $T$ когда все люди будут обслужены.

Примеры:

Вход

2 3 1 2

Ответ

4

Вход

5 6 4 4

Ответ

24

Вход

3 1 2 4

Ответ

8

Замечание

Разберем первый пример. Минута $1$. Первый человек из первой очереди обслужен и уходит из очереди. Теперь $n=1$, $m=3$. Последний человек во второй очереди переходит в конец первой очереди. Теперь $n=2$, $m=2$. Минута $2$. Первый человек из первой очереди обслужен и уходит из очереди. Теперь $n=1$, $m=2$. Первый человек из второй очереди обслужен и уходит из очереди. Теперь $n=1$, $m=1$. Больше ничего не происходит. Минута $3$. Первый человек из первой очереди обслужен и уходит из очереди. Теперь $n=0$, $m=1$. Больше ничего не происходит. Минута $4$. Первый человек из второй очереди обслужен и уходит из очереди. Теперь $n=0$, $m=0$. Все люди обслужены, значит ответ $T=4$. ( Temirlan Baibolov )