로켓

중력이 평범한 곳과는 다르게 작동하는 행성 디스크레티그라비야(Diskretigravija) 의 주민들은 로켓의 효율을 개선하고 시험한다. 이들은 로켓 $N$ 대를 만들었고, 각 로켓이 가능한 한 적은 연료로 정해진 높이에 도달하기를 원한다.

로켓은 다음과 같이 작동한다. 연료가 남아 있는 동안 로켓은 매초 연료 $1$ 단위를 분사하며, 그때마다 수직 속도가

$$\left\lfloor \frac{K}{M+T} \right\rfloor - g$$

만큼 변한다. 여기서

• $K$ 는 그 로켓의 연료 성능,
• $M$ 은 (연료를 뺀) 로켓의 질량,
• $T$ 는 이번에 연료 $1$ 단위를 분사한 직후 남은 연료의 양,
• $g$ 는 행성의 자유낙하 가속도,
• $\lfloor x \rfloor$ 는 $x$ 의 정수 부분(내림)이다. 속도가 음수이면 로켓이 하강하는 것이다.

로켓은 매초 그 순간의 속도만큼 이동하므로, 높이는 매초 현재 속도만큼 변한다. 연료가 모두 떨어지면 속도는 매초 $g$ 씩 감소한다. 로켓이 도달하는 높이란 비행 중 가장 높은 지점을 뜻한다.

예를 들어 $K = 19$, $g = 2$, $M = 3$ 이고 로켓이 처음에 연료 $3$ 단위를 가진 경우를 보자. 첫 번째 초가 시작될 때 로켓은 첫 연료 단위를 분사하고 정확히 $1$ 초 동안 속도 $\left\lfloor \frac{19}{3+2} \right\rfloor - 2 = 1$ 로 상승한다. 그 뒤 속도는 $\left\lfloor \frac{19}{3+1} \right\rfloor - 2 = 2$ 만큼 늘어 초당 $3$ 이 되고, 마지막 연료 단위를 소모하면 다시 $\left\lfloor \frac{19}{3+0} \right\rfloor - 2 = 4$ 만큼 늘어 초당 $7$ 이 된다. 연료가 떨어진 뒤에는 속도가 매초 $2$ 씩 줄어들므로, 로켓은 전부 합쳐 $1 + 3 + 7 + 5 + 3 + 1 = 20$ 의 높이까지 올라간다.

각 로켓이 원하는 높이에 도달하는 데 필요한 최소 연료량을 구하자.

첫째 줄에 두 정수, 로켓의 수 $N$ 과 행성의 자유낙하 가속도 $g$ 가 주어진다.

다음 $N$ 개의 줄에는 각 로켓의 정보가 주어진다. $i+1$ 번째 줄에는 세 정수 $K_i$, $M_i$, $H_i$ 가 주어지며, 각각 $i$ 번째 로켓의 연료 성능, 질량, 그리고 이 로켓이 도달해야 하는 높이를 뜻한다.

$N$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 번째 로켓이 높이 $H_i$ 이상에 도달할 수 있는 최소 연료량을 출력하고, 불가능하면 $-1$ 을 출력한다.

• $1 \le g$
• $1 \le M_i \le K_i \le 10^8$
• $1 \le H_i \le 10^{18}$
• $1 \le N \le 200$