JOI 王国共有 $N$ 座房屋，编号为 $1$ 到 $N$。这些房屋在一条直线上按编号顺序排列。每座房屋里都住着一位市民。居住在房屋 $x$ ($1 \le x \le N$) 的市民被称为市民 $x$。

最近，一种新的病毒出现了，所有市民都感染了该病毒。为了解决这个问题，提出了 $M$ 个治疗方案。方案 $i$ ($1 \le i \le M$) 的费用为 $C_i$。如果执行方案 $i$，会发生以下情况：

在第 $T_i$ 天的傍晚，如果市民 $x$ 满足 $L_i \le x \le R_i$ 且感染了病毒，那么市民 $x$ 将被治愈。

病毒通过邻近的市民传播，方式如下：

如果市民 $x$ ($1 \le x \le N$) 在某天的早晨感染了病毒，那么市民 $x - 1$（如果 $x \ge 2$）和市民 $x + 1$（如果 $x \le N - 1$）会在同一天的中午感染病毒。

已经被治愈的市民可能会再次感染病毒。

作为 JOI 王国的部长，你需要选择一些方案，使得满足以下条件：

条件：在执行完所有选定的方案后，没有市民感染病毒。

可以在同一天执行多个方案。

编写一个程序，给定房屋数量和治疗方案的信息，确定是否可以满足上述条件，如果可以，计算出最小的总费用。

输入格式

从标准输入读取以下数据。所有输入值均为整数。

$N \ M$ $T_1 \ L_1 \ R_1 \ C_1$ $\vdots$ $T_M \ L_M \ R_M \ C_M$

输出格式

输出一行到标准输出。如果无法满足条件，输出 $-1$。否则，输出最小总费用。

数据范围

• $1 \le N \le 1\,000\,000\,000$
• $1 \le M \le 100\,000$
• $1 \le T_i \le 1\,000\,000\,000$ ($1 \le i \le M$)
• $1 \le L_i \le R_i \le N$ ($1 \le i \le M$)
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le M$)

子任务

1. (4 分) $T_i = 1$ ($1 \le i \le M$)。
2. (5 分) $M \le 16$。
3. (30 分) $M \le 5\,000$。
4. (61 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

7

说明 1

在样例 1 中，你可以按如下方式执行方案：

• 在第 2 天的傍晚，执行方案 1，市民 5, 6, 7, 8, 9, 10 被治愈。此时市民 1, 2, 3, 4 感染了病毒。
• 在第 3 天的中午，市民 5 感染了病毒。此时市民 1, 2, 3, 4, 5 感染了病毒。
• 在第 4 天的中午，市民 6 感染了病毒。此时市民 1, 2, 3, 4, 5, 6 感染了病毒。
• 在第 4 天的傍晚，执行方案 5，市民 1, 2, 3 被治愈。此时市民 4, 5, 6 感染了病毒。
• 在第 5 天的中午，市民 3 和 7 感染了病毒。此时市民 3, 4, 5, 6, 7 感染了病毒。
• 在第 5 天的傍晚，执行方案 3，市民 3, 4, 5, 6, 7 被治愈。此后，没有市民感染病毒。

执行方案 1, 3 和 5 的总费用为 7。由于无法在满足条件的情况下使总费用小于 7，因此输出 7。

样例输入 2

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

样例输出 2

-1

说明 2

在样例 2 中，由于无法满足条件，输出 -1。

样例输入 3

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

样例输出 3

7

说明 3

该样例输入满足子任务 1 的限制。