TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1111
  • 题目
  • P1111观光游览
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

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