Autobahn Extra Fee Waiver

There are N racers on a racetrack. The i-th racer races from the beginning of hour \(l_i\) to the end of hour \(r_i\) (both inclusive). Racing costs 1 unit per hour. However, each racer pays only for the first \(t_i\) hours of his race.

For every hour that a racer is driving beyond his paid hours, he is required to pay an extra fee. Nevertheless, the racetrack management is very lenient and collects the extra fee at a given hour only if there are more than K racers who are in their extra (unpaid) period at that hour. In other words, at an hour \(h\), let \(U(h)\) be the number of racers for whom \(h\) lies in their extra period. Then the extra fee charged at hour \(h\) is \(\max(0, U(h)-K)\) (each extra unit costs 1 unit).

The racetrack is running a special promotion: they will select a contiguous time interval of length \(X\) hours. During this interval, if a racer would otherwise be charged an extra fee, the fee for those hours is waived. The goal is to choose the promotion period so that the total amount of extra fee waived (i.e. the money that the racers do not have to pay) is maximized. Compute this maximum amount.

Note: For each racer, his extra period is defined as the time interval from hour \(l_i+t_i\) to hour \(r_i\) (inclusive). If \(l_i+t_i > r_i\), then the racer does not owe any extra fee.

Mathematical formulation:

For every hour \(h\), let \[ U(h) = \text{number of racers with } h \in [l_i+t_i,\; r_i]. \] The extra fee at hour \(h\) is: \[ F(h) = \max(0, U(h)-K). \] If a promotion interval \([L, L+X-1]\) is chosen, then for every hour \(h\) in this interval, the fee \(F(h)\) is waived. Let \[ S = \sum_{h \in [L,L+X-1]} F(h). \] You are to maximize \(S\) over all possible choices of \(L\) (an integer) and output the maximum \(S\).

inputFormat

The first line contains three integers \(N\), \(K\), and \(X\) – the number of racers, the threshold number of racers, and the length of the promotion interval respectively.

Each of the next \(N\) lines contains three integers \(l_i\), \(r_i\), and \(t_i\), where the \(i\)-th racer starts at hour \(l_i\), ends at hour \(r_i\) (inclusive), and has paid for the first \(t_i\) hours.

outputFormat

Output a single integer: the maximum total extra fee waived if the promotion period is chosen optimally.

sample

3 1 2
1 5 2
3 6 1
4 8 3

2