P7214 [JOISC 2020] Treatment Plan

The villagers in JOI Village have recently had an outbreak of COVILLAGE-19!

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.

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 one integer, the minimum total cost. If it is impossible to cure everyone, output $-1$.

#### 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](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) [Day4 C 治療計画 (chiryou keikaku)](https://www2.ioi-jp.org/camp/2020/2020-sp-tasks/day4/treatment.pdf)。 Translated by ChatGPT 5