34898번 - 이루매 사냥

문제

시립대 배봉산에는 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$이하로 지불하여 사냥할 수 있는 이루매 크기 합의 최댓값을 출력한다.

제한

노트