치료 프로젝트

JOI 왕국에는 1번부터 $N$번까지 번호가 매겨진 집 $N$채가 일직선으로 늘어서 있다. 각 집에는 시민이 한 명씩 살며, $x$번 집에 사는 시민을 시민 $x$라고 한다. ($1 \le x \le N$)

새로운 바이러스가 나타나 모든 시민이 감염되었다. 이에 대처하기 위해 $M$개의 치료 프로젝트가 제안되었다. 프로젝트 $i$의 비용은 $C_i$이다. 프로젝트 $i$를 수행하면 다음 일이 일어난다.

$T_i$일 저녁에 $L_i \le x \le R_i$를 만족하는 감염된 시민 $x$가 치료된다.

바이러스는 이웃으로 다음과 같이 퍼진다. 어느 날 아침에 시민 $x$가 감염되어 있으면, 같은 날 정오에 시민 $x-1$($x \ge 2$인 경우)과 시민 $x+1$($x \le N-1$인 경우)이 감염된다. 치료받은 시민도 다시 감염될 수 있다.

선택한 프로젝트를 모두 수행한 뒤 어떤 시민도 감염되어 있지 않도록 프로젝트를 고른다. 같은 날 여러 프로젝트를 수행해도 된다.

이 조건을 만족시킬 수 있는지 판단하고, 만족시킬 수 있다면 총 비용의 최솟값을 구한다.

첫 줄에 $N$과 $M$이 주어진다. 다음 $M$개의 줄에는 각각 $T_i$, $L_i$, $R_i$, $C_i$가 주어진다.

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

한 줄에 출력한다. 조건을 만족시킬 수 없으면 -1을 출력하고, 그렇지 않으면 총 비용의 최솟값을 출력한다.

• $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$)