시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB69443763.793%

문제

시립대 배봉산에는 $1$번부터 $N$번까지 총 $N$마리의 이루매가 살고 있다. 시립대에서는 앞으로 $N$일 동안 이루매 사냥이 진행될 예정이다.

$i$번 이루매의 사냥 $1$일차 크기는 $a_i$이며 매일 이루매를 한 마리 사냥하거나, 휴식을 취하며 하루를 보낼 수 있다. $i$번 이루매를 사냥하기 위해서는 $c_i$의 비용을 지불해야된다.

또한, 어떤 이루매를 사냥하면 그 순간 해당 이루매의 크기는 $0$이 된다.

하지만 이루매들의 도전 정신은 실로 대단하기 때문에, 모든 이루매는 사냥 여부와 관계없이 각 날짜의 행동 이후 하루가 끝날 때 크기가 $b_i$씩 증가한다. 즉, 한 번 사냥한 이루매도 이후 다시 성장하여 또 사냥할 수 있다.

총 비용을 $M$이하로 지불하여 사냥할 수 있는 이루매 크기 합의 최댓값을 구하여라.

입력

첫째 줄에 이루매의 수 $N$과 비용의 한계를 나타내는 정수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100; 0 \le M \le 10\,000)$

이후 N개의 줄에 걸쳐 각 이루매의 정보가 주어진다. 각 줄에는 정수 $a_i, b_i, c_i$가 공백으로 구분되어 주어진다. $(0 \le a_i, b_i \le 100\,000; 0 \le c_i \le 10\,000)$

출력

총 비용을 $M$이하로 지불하여 사냥할 수 있는 이루매 크기 합의 최댓값을 출력한다.

예제 입력 1

3 9
1 9 4
2 7 3
8 10 5

예제 출력 1

38

예제 1의 경우 $1$일차에는 아무 것도 하지 않고, $2$일차에 $1$번 이루매를 사냥해 크기 10을 얻은 뒤, $3$일차에 $3$번 이루매를 사냥해 크기 28을 얻으면 합이 38로 최대가 된다.