J18 实践-6 观光游览

题目描述

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

输入格式

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

输出格式

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

样例输入

3
2
1 2 2
2 3 3
2

样例输出

3

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \le m,n \le 100$，$1 \le k \le m$，$0<v \le 100$。