TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2915
  • Problem
  • P2915出租
    Limits : Time Limit : 10000 MS   Memory Limit : 265536 KB
    Judgment Tips : 1s
    Description

    明年1月到7月何老板将去环球旅行,在这期间,他打算把他在重庆的两套完全一样的房子租出去。现在有5个人想要租何老板的房子,他们的租期和愿意出的租金如下图所示:

    租房者	租期(从第x月租到第y月)	愿意出的租金
    甲	1月到2月                    	10
    乙	4月到7月                 	20
    丙	1月到3月	                    2
    丁	3月到7月	                    3
    茂	1月到6月	                    4
    


    何老板想得到尽可能多的租金,他该把房子租给哪些人呢?

    Input Format

    第1行:两个正整数,t表示何老板的房子从1月到t月可供出租,n表示租房者的人数
    接下来n行:每行三个正整数t1,t2,w, 分别表示第i个租房者的开始时间、结束时间和愿意出的租金隔。

    Output Format

    只有1行: 1个整数,表示能得到的最大租金。

    Sample Input 1

    7 5
    1 2 10
    4 7 20
    1 3 2
    3 7 3
    1 6 4

    Sample Output 1

    35

    Sample Input 2

    288 8
    6 9 66
    28 185 52
    146 173 34
    129 225 35
    133 155 90
    138 175 57
    64 115 65
    223 260 59

    Sample Output 2

    337

    Sample Input 3

    24 10
    12 20 81
    4 4 17
    11 14 60
    1 20 13
    3 3 70
    10 17 31
    2 2 47
    7 11 27
    21 21 86
    4 9 76

    Sample Output 3

    464

    Hint

    样例1是这样实现的:第一套房子租给第1和第4个人,第二套房子租给第2和第3个人。这样最大的租金就为10+20+2+3=35。

    对于30%的数据:1<=t<=500 1<=n<=15 1<=w<=100 1<=t1<=t2<=t
    对于100%的数据:1<=t<=500 1<=n<=100 1<=w<=100 1<=t1<=t2<=t
    这里假设一年至少有t个月