Treatment Project

There are $N$ houses in the JOI kingdom, numbered from 1 to $N$. The houses lie on a line in numerical order. Each house has one citizen. The citizen living in house $x$ ($1 \le x \le N$) is called citizen $x$.

A new virus has infected every citizen. To deal with it, $M$ treatment projects are proposed. Project $i$ costs $C_i$. Performing project $i$ has the following effect.

In the evening of day $T_i$, every infected citizen $x$ with $L_i \le x \le R_i$ is treated.

The virus spreads to neighbors as follows. If citizen $x$ is infected in the morning of some day, then citizen $x-1$ (if $x \ge 2$) and citizen $x+1$ (if $x \le N-1$) become infected at noon of the same day. A treated citizen can be infected again.

Choose some of the projects so that, after all chosen projects are performed, no citizen is infected. Several projects may be performed on the same day.

Determine whether this condition can be satisfied. If it can, find the minimum total cost.

The first line contains $N$ and $M$. Each of the next $M$ lines contains $T_i$, $L_i$, $R_i$, and $C_i$.

N M
T1 L1 R1 C1
.
.
.
TM LM RM CM

Print one line. If the condition cannot be satisfied, print -1. Otherwise, print the minimum total cost.

• $1 \le N \le 1000000000$
• $1 \le M \le 100000$
• $1 \le T_i \le 1000000000$ ($1 \le i \le M$)
• $1 \le L_i \le R_i \le N$ ($1 \le i \le M$)
• $1 \le C_i \le 1000000000$ ($1 \le i \le M$)