Average vampire survivors enjoyer

Time limit: 1s Memory limit: 64MB Input: Output:

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

Cerință

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

Jocul constă în NN runde. În runda ii se pot întâmpla următoarele:

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

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

Date de intrare

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

Date de ieșire

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

Restricții și precizări

  • 1N,t21051 \leq N ,t\leq 2 \cdot 10^5
  • 1R,ai1091 \leq R,a_i \leq 10^9
  • Se garantează faptul că suma NN-urilor pe toate testcase-urile este 2105\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=4P = 4 valorile lui RR pe parcursul jocului vor fi: 9,6,2,69,6,2,6. Observăm că în ultima rundă a4>6a_4 > 6, răspunsul fiind 55.

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

Log in or sign up to be able to send submissions!