有 k 个工人需要粉刷一段长为 N 的栅栏,栅栏从左到右的标号为 1\sim n 。
第 i 个工人现在站在一个栅栏 S_i 前面,他可以选择一段连续的栅栏进行粉刷,第 i 个工人粉刷的栅栏必须包括 S_i 。
然而第 i 个工人的油漆只够他刷 L_i 个栅栏了,每个工人每刷一个栅栏可以得到 P_i 美元的工资。
每一块栅栏只能被一个工人粉刷,工人们的站位互不相同。
作为包工头,你需要求出工人们最大的收入和。
输入共 k+1 行。
第一行两个正整数 N,k 。
接下来 k 行,第 i 行三个正整数 L_i,P_i,S_i ,分别表示第 i 个工人还能刷的栅栏、单位栅栏的工资、工人初始时的站位。
保证 S_i 互不相同。
输出一行一个整数,表示最大的收入和。
8 43 2 23 2 33 3 51 1 7
17
第一个工人粉刷区间 [1, 2] ;
第二个工人粉刷区间 [3, 4] ;
第三个工人粉刷区间 [5, 7] ;
第四个工人不粉刷
1\le N\le 20000 , 1\le k\le 100 , 1\le P_i\le 10000
1\le L_i,S_i\le N