408937: GYM103384 5 Финансовая реформа
Description
Однажды после олимпиады по экономике Мише приснился очень красочный и необычный сон. Мальчик оказался министром финансов Берляндии. Осознав свою значимость, он тут же решил произвести в стране реформу. Раньше в Берляндии использовались банкноты с номиналами $$$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.