测试数据来自 wjszez/2155

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

【输入格式】
输入文件中的第一行为一个整数m（1<=m<=100），表示街道的长度。
第二行一个整数n（1<=n<=100），表示风景点个数。
此后n行，每行描述一个风景点，三个整数x，y和v，表示该风景点是从第x个格子到第y个格子，美学值为v（0<v<=100）。
最后一行一个整数k（1<=k<=m），表示考察的人数。

【输出格式】
输出文件中仅一个整数，表示最大可以得到的分值。

【输入输出样例】
输入：
3
2
1 2 2
2 3 3
2

输出：
3