Today, our airport had $$$N$$$ flights scheduled, initially planned with multiple runways in mind. Unfortunately, due to maintenance issues, only one runway is available, which means not all flights can depart as scheduled. Some flights will leave on time, while others will be postponed until the end of the day.
Airlines, prioritizing customer satisfaction, offer bribes (denoted as $$$b_i$$$ for each flight $$$i$$$) to the airport management to ensure their flights depart on time. Conversely, if a flight is delayed, the airline demands compensation (denoted as $$$c_i$$$ for each flight $$$i$$$).
Your task is to determine the maximum profit the airport can achieve under these conditions, taking into account the bonuses and compensations for each flight.
Additionally, note that there must be a minimum interval of $$$T$$$ time units between consecutive departures, and each plane takes off instantly.
The first line contains two space-separated integers, the number of scheduled flights $$$N$$$, and the minimum interval between flights $$$T$$$.
Each of the next $$$N$$$ lines contain three integers $$$t_i$$$, $$$b_i$$$, $$$c_i$$$, describing the scheduled departure time, the bonus for on-time departure and the compensation required for delay respectively, for the $$$i$$$-th flight. The flights are listed in order of increasing departure time $$$t_i$$$.
The output should contain a single integer $$$P$$$: the maximum profit the airport can achieve.
4 5 2 1000 -100 5 500 -500 7 300 -500 9 1000 -100
1000
Limits
- $$$0 \leq N \leq 10^6$$$
- $$$0 \leq T \leq 10^5$$$
- $$$1 \leq t_i \leq 10^8$$$
- $$$1 \leq b_i \leq 1,000$$$
- $$$-1,000 \leq c_i \leq -1$$$
