问题描述

一条街道被分成 mm 格（1\leq m\leq 1001≤m≤100），还有 nn 个景点（1\leq n\leq 1001≤n≤100），分布在街道上。每个景点可以占据连续的若干格，并且有一个美学值 vv（0\lt v\leq 1000<v≤100）。现要组织 kk 个人考察这个街道（1\leq k\leq m1≤k≤m），每个人考察的区域是连续的若干格（不可为 00 格），且任意两个人考察的区域不得相交，也不得有一个格子无人考察。对于任意一个人，如果它考察的区域中有一个风景点（风景点必须完整的位于这个区域），则它就得到了这个风景点的分值（美学值）。

你的任务是将街道的 mm 个格子分给 kk 个人去考察，使得总的分值最大。

输入格式

第一行一个整数 mm，表示街道的长度。

第二行一个整数 nn，表示风景点个数。

此后 nn 行，每行描述一个风景点，三个整数 x、yx、y 和 vv，表示该风景点是从第 xx 个格子到第 yy 个格子，美学值为 vv。

最后一行一个整数 kk，表示考察的人数。

输出格式

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

输入数据 1

3

2

1 2 2

2 3 3

2

输出数据1

3