variety

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 C_i dollars and giving you 1kg of each type of meat numbered between A_i and B_i 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, A_i, B_i and C_i.

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 ≤ C_i, W ≤ 10⁹, 0 ≤ A_i ≤ B_i < N.

Subtask 1 (8%): A_i = B_i.

Subtask 2 (12%): C_i = 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.