充气球
题目描述
5.1劳动节的组织者计划为此充气m 个气球。他们邀请了n 名助手，第i 名助手充气一个气球需要ti 分钟，但是每次充完 zi 个气球后他会感到疲倦，并休息yi 分钟。现在节日的组织者想知道，在助手们最优工作情况下，所有气球充气完毕的时间，以及每个人各自充了多少气球。（如果助手充完气球需要休息，但他不必再充气球了，则认为他在最后一个气球充气完成后立即结束工作，而不是在休息之后）。
格式
输入格式
输入的第1行包含整数m和n（0≤m≤15000,1≤n≤1000）。 接下来的n行，每行包含三个整数，分别是ti、zi和yi（1≤ti,yi≤100,1≤zi≤1000）。
输出格式
在第一行打印出数字t ，所有气球充气完成所需的时间。
在第二行打印出 n 个数字，每个受邀助手充的气球数。
如果有几个最优解，输出其中任何一个。
样例
输入样例1
1 2
2 1 1
1 1 2
输出样例1
1
0 1
