속독

농부 존의 연례 독서 대회에 소 $K$마리 ($1 \le K \le 1{,}000$)가 모두 참가한다. 이 대회는 $N$쪽 ($1 \le N \le 100{,}000$)짜리 책 한 권을 이해하면서 최대한 빠르게 읽는 것이다.

$i$번 소는 분당 $S_i$쪽 ($1 \le S_i \le 100$)을 읽는 속도, 한 번에 연속으로 읽을 수 있는 최대 시간 $T_i$분 ($1 \le T_i \le 100$), 그리고 읽기를 멈춘 뒤 다시 읽기까지 반드시 쉬어야 하는 최소 휴식 시간 $R_i$분 ($1 \le R_i \le 100$)을 가진다. 소는 분당 $S_i$쪽을 읽지만 한 번에 최대 $T_i$분 동안만 읽을 수 있고, 읽기를 멈추고 쉬기 시작하면 다시 읽기 전에 $R_i$분 동안 쉬어야 한다.

각 소가 책 전체를 다 읽는 데 걸리는 시간을 분 단위로(1분 미만은 올림) 구하여라.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $K$.
• 둘째 줄부터 $K+1$번째 줄까지: $i+1$번째 줄에는 공백으로 구분된 세 정수 $S_i$, $T_i$, $R_i$가 주어진다.

• 첫째 줄부터 $K$번째 줄까지: $i$번째 줄에는 $i$번 소가 책 전체를 읽는 데 필요한 시간을 분 단위로(1분 미만은 올림) 출력한다.

읽기는 항상 1분 단위로 이루어진다. 소는 한 번에 최대 $T_i$분씩(최대 $S_i \cdot T_i$쪽) 몰아서 읽고, 그 뒤에도 읽을 쪽이 남아 있으면 $R_i$분을 쉰 다음 다시 읽는다. 책을 끝내는 마지막 읽기 뒤에는 휴식이 필요 없으며, 1분이 채 되지 않는 마지막 시간도 1분으로 올려서 센다.

예를 들어 10쪽짜리 책에서 분당 2쪽을 최대 4분 동안 읽고 1분을 쉬는 소는, 4분 동안 8쪽을 읽고 1분을 쉰 뒤 남은 2쪽을 1분 만에 읽어 총 6분이 걸린다.