У вас есть возможность выполнять \(n\) квестов. Если вы выполняете \(i\)-й квест, вы получаете \(a_i\) монет. Вы можете выполнить не больше одного квеста в день.
Однако, после того как вы выполнили квест, вы не можете выполнить его снова в течение следующих \(k\) дней. (Например, если \(k=2\) и вы выполняете \(1\)-й квест в \(1\)-й день, тогда вы не сможете выполнить этот квест снова во \(2\)-й или в \(3\)-й день, но сможете его выполнить в \(4\)-й день.)
Заданы два целых числа \(c\) и \(d\). Найдите максимальный \(k\) такой, что возможно получить как минимум \(c\) монет за \(d\) дней. Если таких \(k\) не существует, выведите Impossible. Если \(k\) может быть бесконечно большим, выведите Infinity.
Выходные данные
Для каждого набора входных данных выведите:
- если таких \(k\) не существует, выведите Impossible;
- если \(k\) может быть бесконечно большим, выведите Infinity;
- иначе, выведите одно целое число — максимальный \(k\) такой что возможно получить как минимум \(c\) монет в течение \(d\) дней.
Примечание
В первом тесте, один из способов получить \(5\) монет за \(4\) дня с \(k=2\) состоит в следующем:
- день 1: выполнить квест 2, и получить \(2\) монеты;
- день 2: выполнить квест 1, и получить \(1\) монету;
- день 3: ничего не делать;
- день 4: выполнить квест 2, и получить \(2\) монеты.
Суммарно мы получили \(2+1+2=5\) монет.
Во втором тесте, мы можем получить более \(20\) монет в первый день, выполнив лишь только первый квест. Выполнив первый квест, мы сразу получим \(100\) монет, значит значение \(k\) может быть бесконечно большим, так как нам никогда не понадобится выполнить ещё один квест.
В третьем тесте, что бы мы не делали, мы не можем получить \(100\) монет за \(3\) дня.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1
|
2
Infinity
Impossible
1
12
0
|