logo AlgoBeat OnlineJudge
登录 注册

#214888. [CCPC 2024 哈尔滨站] 农场经营

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

你放弃了编程,来到了三江平原开始务农。在劳动过程中你改掉了作息不规律的毛病,每天你都 工作 个单位时间。现在到了收获的季节,你需要收割并加工你种植的 种作物,对于第 种作物,处理一单位时间该种作物将获得 的收益。为了使每天的工作不会太单调,对于第 种作物,你每天处理它的总时间长度可以是 范围内的整数。

某天,天气预报说第二天的天气不好,于是在今天你需要调整时间安排以尽快抢收作物。具体地说,你能最多选择一种作物,并删除每天处理这种作物的时间范围限制,即删除后处理该作物的总时间长度可以是 范围内的任意整数,而处理其他作物的时间范围不变。你仍然在这一天 工作 个单位时间。

你想知道满足上述条件的情况下,这一天能获得的最大收益是多少。

输入格式

第一行两个整数 (, ),分别表示作物种类数和一天工作时间长度。

接下来 行,每行三个整数 , , 和 (, ),表示作物的收益和总时间长度的限制。

数据保证

输出格式

输出一行一个整数,表示这一天能获得的最大收益。

样例

样例输入 1

5 17
2 3 4
6 1 5
8 2 4
4 3 3
7 5 5

样例输出 1

109