Los ~K (1 \le K \le 1,000)~ macheteros de una brigada millonaria de la zafra azucarera están participando en una competencia de lectura. La competencia consiste en leer un solo libro con ~N (1 \le N \le 100,000)~ páginas tan rápido como sea posible entendiéndolo.

El machetero ~i~ tiene una velocidad de lectura de ~S_i (1 \le S_i \le 100)~ páginas por minuto, un tiempo máximo de lectura consecutiva de ~T_i (1 \le Ti \le 100)~ minutos, y un tiempo mínimo de descanso de ~R_i (1 \le R_i \le 100)~ minutos. El machetero puede leer a un ritmo de Si páginas por minuto, pero solo por ~T_i~ minutos al tiempo. Después él se detiene para descansar, debe descansar por Ri minutos antes de comenzar a leer nuevamente.

Escriba el programa read que determine el número de minutos (redondeados hasta el minuto completo más cercano) que le tomará a cada machetero para leer el libro.

Entrada

Línea 1: Dos enteros separados por espacio: ~N~ y ~K~.

Líneas 2..K+1: La línea i+1 contiene tres enteros separados por espacios: ~S_i, T_i~ y ~R_i~.

Salida

Líneas 1..K+1: La línea i debe indicar cuántos minutos (redondeados hasta el minuto completo más cercano) se requieren para que cada machetero i lea todo el libro.

Ejemplo de Entrada

10 3
2 4 1
6 1 5
3 3 3

Ejemplo de Salida

6
7
7

Detalles de la Entrada

El libro tiene 10 páginas; están compitiendo 3 macheteros. El primer machetero lee con una velocidad de 2 páginas por minuto, puede leer a lo más 4 minutos al tiempo, y debe descansar por 1 minuto después de leer. El segundo machetero lee con una velocidad de 6 páginas por minuto, puede leer a lo más 1 minuto al tiempo, y debe descansar 5 minutos después de leer. El último lee con una velocidad de 3 páginas por minuto, puede leer a lo más 3 minutos a tiempo, y debe descansar 3 minutos después de leer.

Detalles de la Salida

El primer machetero puede leer 8 páginas en 4 minutos, descansar por 1 minuto, y leer las últimas 2 páginas en un minuto. El segundo lee 6 páginas en un minuto, descansa por 5 minutos, y termina en el siguiente minuto. El último lee 9 páginas en 3 minutos, descansa por 3 minutos, y termina en el siguiente minuto.