题目描述

一条街道被分成 $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

样例解释

街道共 $3$ 格，$2$ 个景点：景点 $1$ 占据第 $1\sim2$ 格，美学值 $2$；景点 $2$ 占据第 $2\sim3$ 格，美学值 $3$。考察人数为 $2$。一种最优分配方案为：第一个人考察第 $1$ 格，第二个人考察第 $2\sim3$ 格。此时第二个人完整包含了景点 $2$，获得分值 $3$；第一个人未能完整包含景点 $1$（只考察了第 $1$ 格），不得分。总分为 $3$。

数据范围

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