Description

There are $N$ houses in JOI Village, numbered from $1$ to $N$. Each house has one villager. The villager living in house $i$ is villager $i$.

Now, all villagers in these $N$ houses are infected with the COVILLAGE-19 virus. There are $M$ treatment plans proposed. The $i$-th treatment plan is described as follows: on the night of day $T_i$, the villagers whose numbers are in the interval $[L_i, R_i]$ are cured.

The COVILLAGE-19 virus will continue to spread. On the morning of some day, if villager $i$ is infected, then villager $i+1$ and villager $i-1$ will also be infected. Because the virus is very strong, cured villagers may be infected again.

You are the Prime Minister of JOI Country. You want to choose some plans so that all villagers in JOI Village are cured. You may carry out many plans in one day.

The $i$-th plan costs $C_i$. Find the minimum total cost.

Input Format

The first line contains two integers $N, M$, representing the number of villagers and the number of plans.
The next $M$ lines each contain four integers $T_i, L_i, R_i, C_i$, representing one treatment plan.

Output Format

Output one integer, the minimum total cost.
If it is impossible to cure everyone, output $-1$.

10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1

7

10 5
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1

-1

10 5
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1

7

Hint

Sample 1 Explanation

The execution process is as follows (red means infected, green means cured):

1. On the night of day 2, carry out plan $1$. The situation is:

$$\color{Red}1\ 2\ 3\ 4\color{Green}\ 5\ 6\ 7\ 8\ 9\ 10$$

2. On the morning of day 3, villager $5$ gets infected. The situation is:

$$\color{Red}1\ 2\ 3\ 4\ 5\color{Green}\ 6\ 7\ 8\ 9\ 10$$

3. On the morning of day 4, villager $6$ gets infected. The situation is:

$$\color{Red}1\ 2\ 3\ 4\ 5\ 6\color{Green}\ 7\ 8\ 9\ 10$$

4. On the night of day 4, carry out plan $5$. The situation is:

$$\color{Green}1\ 2\ 3\color{Red}\ 4\ 5\ 6\color{Green}\ 7\ 8\ 9\ 10$$

5. On the morning of day 5, villagers $3, 7$ get infected. The situation is:

$$\color{Green}1\ 2\color{Red}\ 3\ 4\ 5\ 6\ 7\color{Green}\ 8\ 9\ 10$$

6. On the night of day 5, carry out plan $3$. The situation is:

$$\color{Green}1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10$$

Everyone is cured. The total cost of these three plans is $7$, which is the minimum cost.

Sample 2 Explanation

It is impossible to cure all villagers.

Subtasks

Subtask	Special Property	Score
$1$	$T_i = 1$	$4$
$2$	$M \le 16$	$5$
$3$	$M \le 5000$	$30$
$4$	None	$61$

Constraints

For $100\%$ of the testdata, $1 \le N, T_i, C_i \le 10^9$, $1 \le M \le 10^5$, $1 \le L_i \le R_i \le N$.

Notes

Translated from The 19th Japanese Olympiad in Informatics Spring Training Camp Day4 C 治療計画 (chiryou keikaku)。

Translated by ChatGPT 5