~K~ con bò ~(0 < K \le 1000)~ tham dự vào cuộc thi đọc sách hàng năm do nông dân John tổ chức. Trong cuộc thi này, mỗi con sẽ cùng đọc 1 quyển sách có ~N~ trang ~(0 < N \le 10^5)~. Con bò thứ ~k~ có thể đọc với tốc độ ~S_k~ trang/phút, nhưng nó chỉ có thể duy trì tốc độ này trong ~T_k~ phút liên tục. Sau đó, nó phải nghỉ trong ít nhất ~R_k~ phút, kể cả trong trường hợp nó không dùng hết khả năng để đọc ~(0 < S_k, T_k, R_k \le 100)~.

Xác định thời gian nhỏ nhất để mỗi con bò hoàn thành việc đọc sách.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~N~ và ~K~
• Dòng ~2..K + 1~: dòng thứ ~k + 1~ chứa 3 số nguyên dương ~S_k, T_k~ và ~R_k~

Output

• Đưa ra ~K~ dòng. Dòng thứ ~k~ là thời gian tối thiểu (tính theo phút) để con bò thứ ~k~ hoàn thành cuốn sách. Làm tròn kết quả lên số nguyên dương nhỏ nhất và lớn hơn hoặc bằng nó.

Sample

Input #1

10 3
2 4 1
6 1 5
3 3 3

Output #1

6
7
7

Problem source: Kc97ble - Free Contest 21