问题 F: 【非常规DP】观光游览

问题 F: 【非常规DP】观光游览

时间限制: 1 Sec  内存限制: 128 MB
提交: 19  解决: 12
[提交][状态][讨论版][命题人:]

题目描述

      一条街道被分成m格(1≤m≤100),还有n个景点(1≤n≤100),分布在街道上。每个景点可以占据连续的若干格,并且有一个美学值v(0< v≤100)。现要组织k个人考察这个街道(1≤k≤m),每个人考察的区域是连续的若干格(不可为0格),且任意两个人考察的区域不得相交,也不得有一个格子无人考察。对于任意一个人,如果它考察的区域中有一个风景点(风景点必须完整的位于这个区域),则它就得到了这个风景点的分值(美学值)。
      你的任务是将街道的m个格子分给k个人去考察,使得总的分值最大。

 

输入

第一行一个整数m,表示街道的长度。
第二行一个整数n,表示风景点个数。
此后n行,每行描述一个风景点,三个整数x、y和v,表示该风景点是从第x个格子到第y个格子,美学值为v。
最后一行一个整数k,表示考察的人数。

输出

一个整数,表示最大可以得到的分值。

样例输入

3 
2 
1 2 2 
2 3 3 
2

样例输出

3

提示

[提交][状态]