Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more.

The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.

If he had M units of money, what’s the maximum value iSea could get?

Input

There are several test cases in the input.

Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.

Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.

The input terminates by end of file marker.

Output

For each test case, output one integer, indicating maximum value iSea could get.

Sample Input

2 10

10 15 10

5 10 5

3 10

5 10 5

3 5 6

2 7 3

Sample Output

5

11

题目大意就是商店有n件商品, 你有m元, 每件商品商店标价q元, 但是如果身上的钱少于p元老板就不卖你, 这件商品在你心中的价值是v元, 求最大值

01背包的变形题, 和普通的01背包不太一样的地方就是购买的顺序对结果是有影响的, 所以需要对物品进行排序后在根据01背包的状态转移方程进行运算.

至于怎么排序, 应该先买p和q的差值大的, 再买p和q差值小的, 这样是最划算的, 所以就根据p-q来排序, 这里还要注意两点:

• 第二个循环是 j = m;...;j--, 所以排序应该是从小到大, 因为是从后面开始计算的
• 第二个循环中间是小于p而不是小于q

#include <bits/stdc++.h>
using namespace std;

struct object {
    int weight;
    int lessMoney;
    int value;
};

bool cmp(object a, object b) {
    return a.lessMoney-a.weight < b.lessMoney - b.weight;
}

int main() {
    int n, m;
    object objects[5050];
    int dp[5050];
    int a[5050];
    while(~scanf("%d%d", &n, &m)) {
        memset(dp, 0, sizeof dp);
        for(int i = 0; i < n; i++) {
            scanf("%d%d%d", &objects[i].weight, &objects[i].lessMoney, &objects[i].value);
        }
        sort(objects, objects + n, cmp);
        for(int i = 0; i < n; i++) {
            for(int j = m; j >= objects[i].lessMoney; j--) {
                if(dp[j] < dp[j - objects[i].weight] + objects[i].value) {
                    dp[j] = dp[j - objects[i].weight] + objects[i].value;
                }
            }
        }
        printf("%d\n", dp[m]);
    }

    return 0;
}