20200304 - 渡大仙当厨子
时间限制 : 1 秒
内存限制 : 128 MB
渡大仙苦练厨艺，终于成为了某高档酒店的大厨。 每天上班，渡大仙会被要求做 n 份菜。既然是高档酒店，那么客人们当然是很讲究的，尤其对于上菜的时间有很多要求。客人们的要求被分成下列四种：
- 菜品 a 的上菜时间必须比菜品 b 的上菜时间早 d 分钟或者更早。
- 菜品 a 的上菜时间必须比菜品 b 的上菜时间迟 d 分钟或者更迟。
- 菜品 a 的上菜时间在 d 分钟以后(包含 d 分钟)。
- 菜品 a 的上菜时间在 d 分钟之前(包含 d 分钟)。
渡大仙的上班时间记为 0 分钟。为了节约时间，在满足客人们要求的情况下，渡大仙希望最后上的一道菜的时间尽可能的早。（每道菜的上菜时间必须不早于渡大仙的上班时间）
输入
第一行输入一个整数 n，表示一共需要上 n 道菜。
第二行输入一个整数 m，表示客人们的要求数量。
接下里 m 行，每行先输入一个整数 op。
- 如果 op = 1，表示描述里的第 1 种要求，后面跟着三个整数 a, b, d
- 如果 op = 2，表示描述里的第 2 种要求，后面跟着三个整数 a, b, d
- 如果 op = 3，表示描述里的第 3 种要求，后面跟着两个整数 a, d
- 如果 op = 4，表示描述里的第 4 种要求，后面跟着两个整数 a, d
输出
如果渡大仙能满足客人们的要求，输出最后一道菜的上菜时间；否则输出一行 I can't 。
样例
输入
3 5 2 3 2 10 2 2 1 2 2 3 2 5 1 2 3 7 3 3 9
输出
12
输入
3 4 3 1 3 2 3 1 9 2 1 3 -1 1 1 2 5
输出
I can't
输入
17 20 2 6 3 -21 1 8 2 54 3 7 -95 4 11 44 1 5 15 40 3 9 1 3 3 30 3 8 23 2 9 12 -15 4 13 61 2 3 7 31 1 5 10 -15 2 16 1 43 2 12 3 -79 2 14 16 -51 3 6 48 4 7 0 2 10 11 -59 2 12 17 -29 3 4 10
输出
77
提示
对于 30% 的数据：1 ≤ n ≤ 4，1 ≤ m ≤ 10，0 ≤∣ d ∣≤ 10。
对于 60% 的数据：1 ≤ n ≤ 1000，并且输入保证有解。
对于 100% 的数据：1 ≤ n, m ≤ 20000，1 ≤∣ d ∣≤ 10000，1 ≤ a, b ≤ n，a ≠ b。
样例解释 1
1, 2, 3 的上菜时间分别为 0, 2, 12，这样能满足输入客人们的所有要求，并且时间最短。
样例解释 2
t3 ≥ t1 + 9，t1 ≥ t3 − 1，合并以后得到 t1 ≥ t1 + 8，不可能满足客人们的所有要求。