У вас есть возможность выполнять n квестов. Если вы выполняете i-й квест, вы получаете ai
монет. Вы можете выполнить не больше одного квеста в день.
Однако, после того как вы выполнили квест, вы не можете выполнить его снова в течение следующих k дней. (Например, если k=2 и вы выполняете 1 -й квест в 1 -й день, тогда вы не сможете выполнить этот квест снова во 2-й или в 3-й день, но сможете его выполнить в 4 -й день.)
Заданы два целых числа c и d. Найдите максимальный k такой, что возможно получить как минимум c монет за d дней. Если таких k не существует, выведите Impossible. Если k может быть бесконечно большим, выведите Infinity.
Входные данные
Первая строка содержит одно число t (1≤t≤10^4) — количество наборов входных данных.
Первая строка каждого набора содержит три целых числа n,c,d (2≤n≤2⋅10^5; 1≤c≤10^16; 1≤d≤2⋅10^5) — количество квестов, количество необходимых монет и количество дней.
Вторая строка каждого набора содержит n целых чисел a1,a2,…,an (1≤ai≤10^9) — награды за квесты.
Гарантируется что сумма n по всем наборам входных данных не превосходит 2⋅10^5, а сумма d по всем наборам входных данных не превосходит 2⋅10^5.
Выходные данные
Для каждого набора входных данных выведите:
если таких k не существует, выведите Impossible; если k может быть бесконечно большим, выведите Infinity; иначе, выведите одно целое число — максимальный k такой что возможно получить как минимум c монет в течение d дней.
Пример
входные данные
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
Примечание
В первом тесте, один из способов получить 5
монет за 4
дня с k=2
состоит в следующем:
день 1: выполнить квест 2, и получить 2
монеты;
день 2: выполнить квест 1, и получить 1
монету;
день 3: ничего не делать;
день 4: выполнить квест 2, и получить 2
монеты.
Суммарно мы получили 2+1+2=5
монет.
Во втором тесте, мы можем получить более 20
монет в первый день, выполнив лишь только первый квест. Выполнив первый квест, мы сразу получим 100
монет, значит значение k
может быть бесконечно большим, так как нам никогда не понадобится выполнить ещё один квест.
В третьем тесте, что бы мы не делали, мы не можем получить 100
монет за 3
дня.
монет. Вы можете выполнить не больше одного квеста в день.
Однако, после того как вы выполнили квест, вы не можете выполнить его снова в течение следующих k дней. (Например, если k=2 и вы выполняете 1 -й квест в 1 -й день, тогда вы не сможете выполнить этот квест снова во 2-й или в 3-й день, но сможете его выполнить в 4 -й день.)
Заданы два целых числа c и d. Найдите максимальный k такой, что возможно получить как минимум c монет за d дней. Если таких k не существует, выведите Impossible. Если k может быть бесконечно большим, выведите Infinity.
Входные данные
Первая строка содержит одно число t (1≤t≤10^4) — количество наборов входных данных.
Первая строка каждого набора содержит три целых числа n,c,d (2≤n≤2⋅10^5; 1≤c≤10^16; 1≤d≤2⋅10^5) — количество квестов, количество необходимых монет и количество дней.
Вторая строка каждого набора содержит n целых чисел a1,a2,…,an (1≤ai≤10^9) — награды за квесты.
Гарантируется что сумма n по всем наборам входных данных не превосходит 2⋅10^5, а сумма d по всем наборам входных данных не превосходит 2⋅10^5.
Выходные данные
Для каждого набора входных данных выведите:
если таких k не существует, выведите Impossible; если k может быть бесконечно большим, выведите Infinity; иначе, выведите одно целое число — максимальный k такой что возможно получить как минимум c монет в течение d дней.
Пример
входные данные
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
Примечание
В первом тесте, один из способов получить 5
монет за 4
дня с k=2
состоит в следующем:
день 1: выполнить квест 2, и получить 2
монеты;
день 2: выполнить квест 1, и получить 1
монету;
день 3: ничего не делать;
день 4: выполнить квест 2, и получить 2
монеты.
Суммарно мы получили 2+1+2=5
монет.
Во втором тесте, мы можем получить более 20
монет в первый день, выполнив лишь только первый квест. Выполнив первый квест, мы сразу получим 100
монет, значит значение k
может быть бесконечно большим, так как нам никогда не понадобится выполнить ещё один квест.
В третьем тесте, что бы мы не делали, мы не можем получить 100
монет за 3
дня.
; 