Problem Description
Peanut is eating at a KBBQ restaurant, with N different types of meat, numbered 0 to N-1. Unlike most KBBQ places, the food is not free flow. There are M orders that you can make, with order i costing Ci dollars and giving you 1kg of each type of meat numbered between Ai and Bi inclusive.
Peanut wishes to try a wide variety of meat, but doesn't want to get too full, so he wants to eat exactly 1kg of each type of meat. However, as with most KBBQ restaurants, food wastage is charged at W dollars per kg. For each kg of meat Peanut orders but doesn't eat, he would have to pay an additional W dollars.
Help Peanut figure out the minimum amount of money he must spend, in dollars, to try exactly 1kg of every type of meat.
Input
The first line of input will contain three integers, N, M and W.
The next M lines of input will contain three integers each, Ai, Bi and Ci.
Output
The output should contain exactly one integer, the minimum amount of money Peanut must spend, in dollars. If no possible solution will allow Peanut to try every type of meat, print -1.
Limits
For all subtasks: 1 ≤ N, M ≤ 300 000, 0 ≤ Ci, W ≤ 109, 0 ≤ Ai ≤ Bi < N.
Subtask 1 (8%): Ai = Bi.
Subtask 2 (12%): Ci = 1, W = 0.
Subtask 3 (24%): W = 0.
Subtask 4 (23%): 1 ≤ N, M ≤ 1000.
Subtask 5 (33%): No additional constraints.
Sample Input
3 3 1
0 1 2
1 2 2
0 2 6
Sample Output
5
Explanation
It is optimal for Peanut to buy the first and second orders, costing a total of $4. Since he will get 2kg of meat 1, he will pay a $1 fine for wasting 1kg of food. This will cost a total of $5.