TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1111
  • Problem
  • P1111观光游览
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    3
    2
    1 2 2
    2 3 3
    2

    Sample Output

    3