Організатори дитячого свята планують надути для нього повітряних кульок. З цією метою вони запросили \(𝑁\) добровільних помічників, \(𝑖\) -й серед яких надуває кульку за \(𝑇_𝑖\) хвилин, проте щоразу після надування \(𝑍_𝑖\) кульок втомлюється і відпочиває \(𝑌_𝑖\) хвилин.

Тепер організатори свята хочуть дізнатися, через який час будуть надуті всі кульки при найбільш оптимальній роботі помічників, і скільки кульок надує кожен з них. (Якщо помічник надув кульку, і повинен відпочити, але більше кульок йому надувати не доведеться, то вважається, що він закінчив роботу відразу після закінчення надування останньої кульки, а не після відпочинку).

Формат вхідних даних

У першому рядку вхідних даних задаються числа \(𝑀\) і \(𝑁\) (\(0 \le 𝑀 \le 15000\), \(1 \le 𝑁 \le 1000\)).

Наступні \(𝑁\) рядків містять по три цілих числа - \(𝑇_𝑖 , 𝑍_𝑖, 𝑌_𝑖\) відповідно (\(1 \le 𝑇_𝑖 , 𝑌_𝑖 \le 100\), \(1 \le 𝑍_𝑖 \le 100\))

Формат вихідних даних

Виведіть у першому рядку число \(𝑇\) - час, за який будуть надуті всі кульки.

У другому рядку виведіть \(𝑁\) чисел - кількість кульок, надутих кожним із запрошених помічників. Розділяйте числа пробілами. Якщо розподілів кульок кілька, виведіть будь-яку з них.

Приклад вхідних даних

2 2
1 1 1
1 1 1

Приклад вихідних даних

1
1 1

Приклад вхідних даних

3 2
2 2 5
1 1 10

Приклад вихідних даних

4
2 1