태종대 낚시 맛집

면접 대비

시간 제한1초메모리 제한1024 MB

요약

먹성, 크기, 가격이 주어진 물고기들에 대해 떡밥을 최대 한 번 원하는 만큼 던져 떡밥 비용을 뺀 최대 이익을 구한다.

난이도: 쉬움10점 중 3점
유형: 시뮬레이션, 정렬, 그리디, 완전 탐색
정답자: 아직 제출이 없습니다

문제

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

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

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

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

입력

첫 번째 줄에 물고기의 수를 나타내는 정수 $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$ )

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

출력

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

예제2

예제 1

입력

예상 출력

예제 2
입력
```
2
30
100 1 100
50 2 120
```
예상 출력
```
0
```