35508번 - Good Bye, 토마토!

https://www.acmicpc.net/problem/7576

2017년부터 요리 강좌를 수강한 브루는 $N$종류의 토마토 요리를 만들 수 있는 요리사이다. 약 10년간 내공을 쌓아 온 브루는 천하제일 토마토 요리 대회에 참가하기로 했다. 이 대회에는 두 명의 저명한 심사 위원이 있다.

• wookje: 천하제일 요리 대회의 창시자이자 인플루언서이다.
• evenharder: 토마토의 익힘 정도가 이븐한지를 중시하는 셰프이다.

대회는 총 $D$분 동안 진행된다. 브루는 대회 시간 안에 요리를 만들어, 완성한 요리를 두 심사 위원에게 원하는 만큼 제출할 수 있다. 하나의 요리를 제출할 때마다 두 심사 위원은 모두 요리를 먹어 보고 각각 점수를 매긴다. 두 심사 위원의 미적 취향은 서로 다르므로, 같은 요리라도 심사 위원에 따라 받는 점수가 다를 수 있다. 브루의 최종 점수는 wookje 심사 위원이 매긴 점수 중 최댓값과 evenharder 심사 위원이 매긴 점수 중 최댓값의 합이다.

브루는 $i$번 요리를 제출했을 때 wookje 심사 위원에게서는 $A_i$점을, evenharder 심사 위원에게서는 $B_i$점을 받을 수 있다고 분석했다. $i$번 요리를 만드는 데에는 $T_i$분이 소요되며, 브루는 동시에 두 개 이상의 요리를 만들 수 없다. 심사 위원이 요리를 심사하는 데 걸리는 시간은 무시한다.

브루의 분석이 모두 정확하다고 할 때, 브루가 대회에서 받을 수 있는 최종 점수의 최댓값을 구하여라.

첫째 줄에는 요리의 수를 나타내는 정수 $N$과 제한 시간을 나타내는 정수 $D$가 공백으로 구분되어 주어진다.

다음 $N$개의 줄에는 각 요리에 대한 정보가 주어진다. 이 중 $i$번째 줄에는 세 정수 $T_i$, $A_i$, $B_i$가 공백으로 구분되어 주어진다. 이는 $i$번 요리를 만드는 데 $T_i$분이 걸리며, 해당 요리를 제출했을 때 wookje 심사 위원에게서 $A_i$점, evenharder 심사 위원에게서 $B_i$점을 받을 수 있음을 의미한다.

첫째 줄에 브루의 분석하에서, 브루가 최대로 얻을 수 있는 점수를 출력한다.

• $1 \le N \le 2 \times 10^5$
• $1 \le D \le 10^9$
• $1 \le T_i \le D$ ($1 \le i \le N$)
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• $1 \le B_i \le 10^9$ ($1 \le i \le N$)