408937: GYM103384 5 Финансовая реформа

5. Финансовая реформаограничение по времени на тест1 секундаограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Однажды после олимпиады по экономике Мише приснился очень красочный и необычный сон. Мальчик оказался министром финансов Берляндии. Осознав свою значимость, он тут же решил произвести в стране реформу. Раньше в Берляндии использовались банкноты с номиналами $$$1$$$, $$$10$$$, $$$100$$$ и $$$1\,000$$$ бурлей. Мише данная система показалась крайне банальной, поэтому он решил придумать что-то свое.

Мальчик выбрал два целых числа $$$x$$$ и $$$y$$$ ($$$x \leq y$$$) и заявил, что теперь в Берляндии будут использоваться только банкноты с номиналами $$$x,~x + 1,~x + 2,~\ldots,~y$$$ бурлей. Вскоре реформа была принята и вступила в силу, однако населению страны это совсем не понравилось. Недовольства начались из-за того, что теперь, используя новые банкноты, можно было набрать далеко не любую сумму.

Например, если Мишей были выбраны числа $$$x = 5$$$ и $$$y = 7$$$, то невозможно набрать суммы $$$1$$$, $$$2$$$, $$$3$$$ и $$$4$$$ бурлей. Также не получится набрать суммы $$$8$$$ и $$$9$$$ бурлей. Если же выбрать числа $$$x = y = 2$$$, то невозможно будет набрать любую нечетную сумму.

Миша, находясь на грани увольнения, решил успокоить население Берляндии и предъявить такое минимальное число $$$N$$$, что при помощи новых банкнот возможно набрать любую сумму, начиная с $$$N$$$. Таким образом, должно быть возможно набрать суммы $$$N$$$ бурлей, $$$N + 1$$$ бурлей, $$$N + 2$$$ бурлей, и так далее. Помогите Мише найти искомое число $$$N$$$ и избежать увольнения.

Входные данные

В первой строке входных данных записано целое число $$$x$$$ — минимальный номинал новых банкнот.

Во второй строке записано целое число $$$y$$$ ($$$1 \leq x \leq y \leq 2 \cdot 10^9$$$) — максимальный номинал новых банкнот.

Выходные данные

Выведите одно натуральное число $$$N$$$ — минимальное число, такое, что при помощи банкнот с номиналами $$$x,~x + 1,~x + 2,~\ldots,~y$$$ можно набрать любую сумму, начиная с $$$N$$$ бурлей.

Если такого числа не существует, в качестве ответа выведите $$$-1$$$.

Система оценки

Решения, правильно работающие только для случаев, когда $$$x$$$ и $$$y$$$ не превосходят $$$10^4$$$, будут оцениваться в $$$40$$$ баллов.

ПримерыВходные данные

5
7

Выходные данные

10

Входные данные

2
2

Выходные данные

-1

Входные данные

1900000000
2000000000

Выходные данные

36100000000

Примечание

В первом примере имеются банкноты трех номиналов: $$$5, 6$$$ и $$$7$$$ бурлей. Ниже перечислены суммы, которые можно набрать при помощи данных банкнот:

• $$$5 = 5$$$,
• $$$6 = 6$$$,
• $$$7 = 7$$$,
• $$$10 = 5 + 5$$$,
• $$$11 = 5 + 6$$$,
• $$$12 = 5 + 7$$$,
• $$$13 = 6 + 7$$$,
• $$$\ldots$$$

Можно показать, что при помощи банкнот данных номиналов возможно набрать любую сумму, начиная с $$$10$$$ бурлей.

Во втором примере есть банкноты всего одного номинала: $$$2$$$ бурля. При помощи данных банкнот можно набрать только любую чётную сумму: 2, 4, 6, .... Таким образом, искомого числа $$$N$$$ не существует.

Обратите внимание, что ответ может получиться достаточно большим, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.