The orator loves butter cakes. He prepares to make $m$ butter cakes using $n$ types of ingredients, where the $i$-th butter cake is made from ingredients in the range $[l_i, r_i]$.

The little murloc wants to poison the orator. He can perform the following two types of operations:

1. Add a bottle of poison to a specific ingredient, at a cost of $k$, where $k$ is a given positive integer.
2. Add a bottle of poison to a specific butter cake, at a cost of $1$.

Note that the same ingredient or the same butter cake can be poisoned multiple times.

If, for the $i$-th butter cake, the sum of the number of poisons in all its constituent ingredients plus the number of poisons in the butter cake itself is $\ge a_i$, then the butter cake is considered highly toxic, where $a_i$ is a given positive integer.

The little murloc wants to make all butter cakes highly toxic. What is the minimum cost?

Input

The first line contains three positive integers $n, m, k$, representing the number of ingredients, the number of butter cakes, and the cost of poisoning an ingredient, respectively.

The following $m$ lines each contain three integers $l_i, r_i, a_i$, with meanings as described in the problem statement.

Output

Output a single integer representing the minimum cost.

Constraints

For all data, $1 \le n, m \le 5 \times 10^5$, $1 \le k \le 5$, $1 \le a_i \le 10^9$.

Examples

Input 1

3 2 1
1 2 1
2 3 2

Output 1

2