Problem D: 地铁（subway）

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

B 市的地铁历史悠久，小雪和小可可乘坐的 X 号线是环形路线，上面分布着 n 个车站，
相邻两个车站之间的铁路长度为正整数。现在小雪进行了一些观察，得到了 m 条信息，第 i 条信息是如下形式之一：
1.环上顺时针由 Si到 Ti的一段距离不小于一个给定的值 Li（Si 和 Ti是两个车站）；
2.环上顺时针由 Si到 Ti的一段距离不大于一个给定的值 Li。
小雪想要你计算最后 X 线地铁的总长度有多少种不同的合法取值。

Input

第一行两个空格隔开的正整数 n 和 m。
下面 m 行，第 i 行四个空格隔开的正整数 typei , Si , Ti , Li，其中 typei∈ {1, 2} 表示信息的类型。车站顺时针编号为从 1 开始的连续整数。保证 1 ≤ Si , Ti ≤ n 且 Si= Ti。

Output

仅一行一个整数，表示所求答案。如果有无穷种取值，请输出 -1。

保证答案不为0，即至少有一种可能的方案。

Sample Input复制

4 6
1 1 3 3
2 2 4 5
1 2 4 4
1 3 1 4
2 4 2 5
1 4 2 3

Sample Output复制

4

提示

【样例解释】
定义数组 d[1..4]，其中 d[i] 表示 i 号车站顺时针到 i + 1
号车站的铁路长度。
1.d = [1, 2, 2, 2]，总长度为 7；
2.d = [1, 2, 2, 3]，总长度为 8；
3.d = [1, 2, 2, 4]，总长度为 9；
4.d = [1, 2, 3, 4]，总长度为 10。
可以证明，不存在其他的可能长度，于是答案为 4。