RoAlgo Educational Round #3 | Average vampire survivors enjoyer

Bahoi nu face tema de vacanță la mate, el dă grind pe vampire survivors.

Cerință

Inițial HP-ul lui Bahoi este de $R$ unități. Există $N$ monștri, al $i$-lea monstru având puterea de $a_i$ unități. El are la îndemână o bucată dintr-un floor chicken care are puterea de a-i reda $P$ unități din HP.

Jocul constă în $N$ runde. În runda $i$ se pot întâmpla următoarele:

• $R$ devine $R - a_i$. Dacă în urma operației $R$ scade sub $1$ ($R \leq 0$), atunci Bahoi pierde și jocul se termină.
• Dacă supraviețuiește, $R = R + P$.

Jocul se încheie după cele $N$ runde. Află care este $P$-ul minim pozitiv, astfel încât după finalizarea celor $N$ runde Bahoi să rămână în viață, iar în cazul în care Bahoi nu poate câștiga indiferent de valoarea lui $P$, se va afișa $-1$.

Date de intrare

Pe prima linie se află $t$, numărul de test cases. Pe prima linie a fiecărui test case se află trei numere $N$ și $R$, iar pe următoare linie se află exact $N$ numere separate prin câte un spațiu.

Date de ieșire

Se vor afișa $t$ linii, răspunsurile la cele $t$ test case-uri.

Restricții și precizări

• $1 \leq N ,t\leq 2 \cdot 10^5$
• $1 \leq R,a_i \leq 10^9$
• Se garantează faptul că suma $N$-urilor pe toate testcase-urile este $\leq 2 \cdot 10^5$.

Exemplu

stdin

7
4 14
5 7 8 7 
2 17
2 6 
5 11
2 8 7 8 2 
6 5
4 5 3 4 4 1 
8 3
2 1 9 2 1 2 9 4 
2 12
9 5 
4 18
4 3 4 7

stdout

5
0
5
5
5
3
1

Explicație

În primul test case, pentru $P = 4$ valorile lui $R$ pe parcursul jocului vor fi: $9,6,2,6$. Observăm că în ultima rundă $a_4 > 6$, răspunsul fiind $5$.

În cel de-al doilea test case pentru $P = 0$, Bahoi poate câștiga jocul.