The popular fast food chain «McDuck's» opened a new branch in Berland. The restaurant has k stoves. To cook a burger, you need to fry a patty for a minute on one of the stoves, so a restaurant can cook no more than k burgers per minute.
It is known that in «McDuck's» n clients will come. The i-th of them will arrive at time t
i, order x
i burgers and be ready to pay c
i burles for them. Each client is ready to wait for an order for w minutes, and if w minutes after arrival he has not received x
i burgers, he will not pay anything. At the same time, each client is ready to receive only fresh burgers, that is, only those for which the burgers were fried not earlier than the time t
i. Due to such complex requirements, the restaurant will not always be able to fulfill all the orders of all customers.
The restaurant managers were interested in the maximum profit McDuck's could make. Help them answer this difficult question. We can assume that no money is spent on cooking burgers.
Input
The first line contains three integers n, k and w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — the number of clients, the number of plates and the waiting time for the client, respectively.
The next n lines contain descriptions of clients, consisting of three integers — t
i, x
i, c
i (1 ≤ t
i, x
i sub>, c
i ≤ 10
9) — the time (in minutes) of arrival of the i-th customer, the number of burgers he will order and the number of burles he is willing to pay, respectively. Clients are listed in ascending order of arrival time, i.e. for any i > 1 it is true that t
i−1 ≤ t
i.
Imprint
In a single line print a single number — maximum restaurant profit.
Note
In the first test example, the first patty can be fried at time 0, and then at time 1 it will be ready and can be served in a burger to the first client. At time 1, you can put another patty to fry, it will be ready at time 2 and can be served in a burger to the second client.
Examples
| # |
Input |
Output |
| 1 |
2 1 1
1 1 5
1 1 7
| 12 |
| 2 |
3 2 2
1 6 8
2 5 10
3 4 4
| 12 |