题目描述

一条巡逻路线上有 $n$ 个岗哨，依次编号 $1\sim n$。记 $s_i$ 为前 $i$ 个岗哨中安排的值班人数（$s_0=0$）。

安排必须满足：相邻两个岗哨之间最多新增 $1$ 人，即对每个 $1\le i\le n$ 有 $0\le s_i-s_{i-1}\le 1$。

上级还给出了 $m$ 条要求，第 $j$ 条形如「第 $l_j$ 到第 $r_j$ 个岗哨中」：

• 类型 $1$：至少安排 $k_j$ 人；
• 类型 $2$：至多安排 $k_j$ 人；
• 类型 $3$：恰好安排 $k_j$ 人。

请在所有要求都能满足的前提下，求出 $n$ 个岗哨安排人数的最小值。若要求互相矛盾，输出 $-1$。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行四个整数 $l_j,r_j,k_j,t_j$，含义如上。

输出格式

一行一个整数，表示最少安排的总人数；矛盾时输出 $-1$。

输入输出样例 #1

输入 #1

3 1
1 3 2 3

输出 #1

2

输入输出样例 #2

输入 #2

2 1
1 1 2 1

输出 #2

-1

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 5000$，$0\le m\le 5000$，$1\le l_j\le r_j\le n$，$0\le k_j\le n$，$t_j\in\{1,2,3\}$。