Problem Background

Due to the excessive number of data points, please test the additional 3 sets of data here.

The villagers of JOI Village have recently been struck by the COVILLAGE-19 outbreak!

Problem Description

JOI Village has \( N \) houses numbered from 1 to \( N \), with each house inhabited by a villager. The \( i \)-th house is occupied by villager \( i \).

Currently, all \( N \) villagers are infected with the COVILLAGE-19 virus. \( M \) treatment plans have been proposed. The \( i \)-th plan describes that on the evening of day \( T_i \), villagers within the range \([L_i, R_i]\) are cured.

The COVILLAGE-19 virus continues to spread. If villager \( i \) is infected in the morning, then villagers \( i+1 \) and \( i-1 \) will also become infected. Due to the potent nature of the virus, cured villagers may be reinfected.

You are the Prime Minister of JOI Kingdom, and you need to select some plans to ensure that all villagers in JOI Village are cured. Multiple plans can be carried out in a single day.

Each plan \( i \) costs \( C_i \). Find the minimum total cost.

Input Format

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

Output Format

A single line containing an integer representing the minimum cost.
If it is impossible to cure all villagers, output \(-1\).

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

Sample Input #2

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

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

7

Notes

Sample 1 Explanation

The execution process is as follows (red indicates infection, green indicates cure):

1. On the second evening, execute the first plan:

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

1. On the third morning, villager 5 gets infected:

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

1. On the fourth morning, villager 6 gets infected:

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

1. On the fourth evening, execute the fifth plan:

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

1. On the fifth morning, villagers 3 and 7 get infected:

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

1. On the fifth evening, execute the third plan:

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

All villagers are cured, with a total cost of 7, which is the minimum cost.

Sample 2 Explanation

It is impossible to cure all villagers.

Subtasks

For 100% of the data, \( 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 第１９回日本情報オリンピック　春季トレーニング合宿 Day4 C 治療計画.

见题面 Input 部分

见题面 Output 部分