J17 实践-10 捆绑销售

题目描述

最近，佩奇去了一个古老的国家。在很久之前，它是世界上最富有和最强大的王国。因此，这个国家的人民非常自豪，即使他们的国家现在已经不再那么富有了。

其中，那里的商人是最为典型的，他们每个人只卖一件商品，价格是$p_i$，但如果你的钱少于$qi$，他们会拒绝与你交易，评估每件商品的价值为$vi$。

如果他有$M$个单位的钱，佩奇能得到的最大价值和是多少？

输入格式

第一行$2$个整数，$N,M$ ； 接下来 $N$行每行三个整数，分别表示 $p_i，q_i，v_i$ ；

输出格式

一个非负整数，表示最大价值和。

样例输入1

2 10
10 15 10
5 10 5

样例输出1

5

样例输入2

3 10
5 10 5
3 5 6
2 7 3

样例输出2

11

数据范围

$100\%$ 的数据：$1 \leq N,M \leq 3000; p_i\leq q_i\leq1000;v_i\leq1000$。