Cure All Villagers

In JOI Village there are $N$ houses numbered from $1$ to $N$, with one villager living in each house (villager $i$ lives in house $i$). Initially, all villagers are infected with the COVILLAGE-19 virus. There are $M$ treatment plans proposed. The $i$-th treatment plan is described by four integers $T_i$, $L_i$, $R_i$, and $C_i$, meaning that on the evening of day $T_i$, the villagers living in houses in the interval $[L_i,R_i]$ are cured.

However, the virus is extremely potent and spreads every morning: on any morning, if villager $i$ is infected, then his neighbors (villager $i-1$ and villager $i+1$, if they exist) will also become infected. Note that even if a villager was cured the previous evening, they may become infected again if one of their neighbors is infected in the following morning.

A single day may have many treatment plans. In order to permanently cure all villagers, there must exist a day during which the treatments applied cure all houses (i.e. the union of the intervals of treatment plans applied that evening covers the entire range $[1,N]$), so that no one is left infected to re‐infect their neighbors the next morning.

Your task as the Prime Minister is to choose some of the treatment plans (possibly more than one on the same day) so that on at least one day the entire village is cured, and to minimize the total cost spent. Compute the minimum total cost needed. If it is impossible to cure the entire village in one day using the available treatment plans, output $-1$.

inputFormat

The input is given in the following format:

$N\ M$
$T_1\ L_1\ R_1\ C_1$
$T_2\ L_2\ R_2\ C_2$
...
$T_M\ L_M\ R_M\ C_M$

Where:
$1 \leq N \leq$ (an upper bound), the number of houses.
$1 \leq M \leq$ (an upper bound), the number of treatment plans.
$1 \leq T_i$, the day of the treatment plan.
$1 \leq L_i \leq R_i \leq N$, the interval of houses cured by the plan.
$1 \leq C_i$, the cost of the plan.

outputFormat

Output a single integer representing the minimum total cost to permanently cure all villagers, or $-1$ if it is impossible.

sample

3 3
2 1 1 3
2 2 3 4
1 1 3 10

7