33847번 - 태종대 낚시 맛집

문제

태종대에는 낚시 맛집이라 불리는 낚시 포인트가 있다. 낚시 맛집에는 서로 다른 크기의 $n$마리의 물고기가 살고 있다. 각 물고기는 먹성, 크기, 가격이 다양해 어떤 물고기가 낚이는 지에 따라 낚시 결과가 결정된다.

산지니는 물고기를 낚기 위해 떡밥을 던져서 물고기를 유인하려 한다. 너무 떡밥을 자주 던지면 물고기가 놀라 도망갈 수 있으므로 최대 한 번 떡밥을 원하는 만큼 던지고자 한다. 산지니가 떡밥을 낚시 맛집에 던지면 아래 과정이 반복되어 물고기가 유인된다.

1. 낚시 포인트에 남은 떡밥의 개수 $t$보다 작거나 같은 먹성의 물고기 중 가장 크기가 큰 물고기가 유인된다.
2. 유인된 물고기는 자기 먹성 만큼의 떡밥을 먹는다.
3. 산지니는 낚시의 달인이기 때문에 유인된 물고기를 항상 낚을 수 있다. 산지니는 낚은 물고기의 가격만큼의 수익을 얻는다.

산지니는 물고기가 더 이상 유인되지 않거나 원하는 경우 낚시를 종료하고 이익을 계산하러 집으로 간다. 떡밥의 가격과 각 물고기의 먹성, 크기, 판매 가격이 주어질 때 산지니가 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오. 산지니가 얻은 이익은 낚은 물고기의 가격 합에서 사용한 떡밥의 가격을 뺀 값이다.

입력

첫 번째 줄에 물고기의 수를 나타내는 정수 $n$이 주어진다. (1ドル \leq n \leq 100$)

두 번째 줄에 떡밥 한 개의 가격 $c$가 주어진다. (1ドル \leq c \leq 100$)

세 번째 줄부터 $n$개의 줄에 걸쳐 물고기의 먹성 $x,ドル 크기 $s,ドル 가격 $w$이 한 줄에 하나씩 공백으로 구분되어 주어진다. (1ドル \leq x \leq 100; 1 \leq s \leq 10,000円; 1 \leq w \leq 10^7$)

모든 물고기의 크기는 서로 다르다. 주어지는 모든 수는 정수이다.

출력

산지니가 얻을 수 있는 최대 이익을 출력한다.

제한

힌트