#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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*and

_{i}*B*inclusive.

_{i}
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*and

_{i}*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^{9}, 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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 8 | 20 | 1s | 256MB | Minimum |

2 | 12 | 20 | 1s | 256MB | Minimum |

3 | 24 | 40 | 1s | 256MB | Minimum |

4 | 23 | 21 | 1s | 256MB | Minimum |

5 | 33 | 101 | 1s | 256MB | Minimum |

6 | 0 | 1 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o variety -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512