7226번 - Raketa 다국어

문제

Planetos Diskretigravijos (kurios gravitacija veikia kitaip, nei įprasta) gyventojai tobulina ir testuoja raketų efektyvumą. Tam jie pagamino $N$ raketų, ir nori, kad kiekviena iš jų pasiektų tam tikrą aukštį, sunaudodama kuo mažiau kuro.

Šios raketos veikia taip: kol raketoje yra kuro, ji kiekvieną sekundę išmeta po 1 kuro vienetą ir pakeičia savo vertikalų greitį (kuris bus neigiamas, jei raketa leidžiasi) per $\left\lfloor \frac{K}{M+T} \right\rfloor - g$ kur

• $K$ yra tos raketos kuro gerumas,
• $M$ – raketos (be kuro) masė,
• $T$ – likusio kuro kiekis po to, kai išmetamas 1ドル$ kuro vienetas,
• $g$ – planetos laisvojo kritimo pagreitis,
• $\lfloor x \rfloor$ – skaičiaus $x$ sveikoji dalis.

Kai raketoje baigiasi kuras, jos greitis kas sekundę sumažėja $g$ greičio vienetų.

Panagrinėkime pavyzdį, kai $K = 19,ドル $g = 2,ドル $M = 3$ ir raketa pradžioje turi 3ドル$ kuro vienetus. Pirmosios sekundės pradžioje raketa išmeta pirmą kuro vienetą ir lygiai sekundę kyla greičiu $\left\lfloor \frac{19}{3+2} \right\rfloor - 2 = 1$. Po sekundės greitis padidėja dar per 2ドル$ iki 3ドル$ atstumo vienetų per sekundę, o sunaudojus paskutinį kuro vienetą raketos greitis padidėja dar per 4ドル$ iki 7ドル$ vienetų per sekundę. Pasibaigus kurui raketos greitis kas sekundę sumažėja per 2ドル,ドル taigi iš viso raketa pakyla į 1ドル + 3 +たす 7 +たす 5 +たす 3 +たす 1 =わ 20$ vienetų aukštį.

Padėkite raketų testuotojams nustatyti, kiek mažiausiai kuro reikia jų raketoms, kad pakiltų į norimą aukštį.

입력

Pirmojoje įvesties eilutėje pateikti du sveikieji skaičiai: raketų skaičius $N$ ir planetos laisvojo kritimo pagreitis $g$.

Likusiose $N$ eilučių surašyti raketų parametrai. $i + 1$-ojoje eilutėje pateikti sveikieji skaičiai $K_i,ドル $M_i$ ir $H_i$ – $i$-tosios raketos kuro gerumas, masė ir aukštis, į kurį ši raketa turi pakilti.

출력

Išveskite $N$ eilučių, kuriose būtų po vieną sveikąjį skaičių: $i$-tojoje eilutėje išveskite mažiausią kuro kiekį, su kuriuo $i$-toji raketa gali pakilti į aukštį $H_i,ドル arba $-1,ドル jei tai neįmanoma.

제한

• 1ドル ≤ g, M_i ≤ K_i ≤ 10^8$
• 1ドル ≤ H_i ≤ 10^{18}$
• 1ドル ≤ N ≤ 200$

힌트