TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2915
  • 题目
  • P2915何老板出租房
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

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

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


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

    输入格式

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

    输出格式

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

    样例输入

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

    样例输出

    35

    提示

    样例是这样实现的:第一套房子租给第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个月