2559: 蒜头君当大厨

蒜头君苦练厨艺，终于成为了某高档酒店的大厨。

每天上班，蒜头君会被要求做 $n$n 份菜。既然是高档酒店，那么客人们当然是很讲究的，尤其对于上菜的时间有很多要求。客人们的要求被分成下列四种：

1. 菜品 $a$a 的上菜时间必须比菜品 $b$b 的上菜时间早 $d$d 分钟或者更早。

2. 菜品 $a$a 的上菜时间必须比菜品 $b$b 的上菜时间迟 $d$d 分钟或者更迟。

3. 菜品 $a$a 的上菜时间在 $d$d 分钟以后(包含 $d$d 分钟)。

4. 菜品 $a$a 的上菜时间在 $d$d 分钟之前(包含 $d$d 分钟)。

蒜头君的上班时间记为 $0$0 分钟。为了节约时间，在满足客人们要求的情况下，蒜头君希望最后上的一道菜的时间尽可能的早。（每道菜的上菜时间必须不早于蒜头君的上班时间）

输入格式

第一行输入一个整数 $n$n，表示一共需要上 $n$n 道菜。

第二行输入一个整数 $m$m，表示客人们的要求数量。

接下里 $m$m 行，每行先输入一个整数 $op$op。

• 如果 $op=1$op=1，表示描述里的第 $1$1 种要求，后面跟着三个整数 $a,b,d$a,b,d
• 如果 $op=2$op=2，表示描述里的第 $2$2 种要求，后面跟着三个整数 $a,b,d$a,b,d
• 如果 $op=3$op=3，表示描述里的第 $3$3 种要求，后面跟着两个整数 $a,d$a,d
• 如果 $op=4$op=4，表示描述里的第 $4$4 种要求，后面跟着两个整数 $a,d$a,d

输出格式

如果蒜头君能满足客人们的要求，输出最后一道菜的上菜时间；否则输出一行 I can't。

数据范围和约定

对于 $30\%$30% 的数据：$1 \le n \le 4$1≤n≤4，$1 \le m \le 10$1≤m≤10，$0 \le \mid d \mid \le 10$0≤∣d∣≤10。

对于 $60\%$60% 的数据：$1 \le n \le 1000$1≤n≤1000，并且输入保证有解。

对于 $100\%$100% 的数据：$1 \le n, m \le 20000$1≤n,m≤20000，$1 \le \mid d \mid \le 10000$1≤∣d∣≤10000，$1 \le a, b \le n$1≤a,b≤n，$a \ne b$a≠b。

样例解释 1

$1, 2, 3$1,2,3 的上菜时间分别为 $0, 2, 12$0,2,12，这样能满足输入客人们的所有要求，并且时间最短。

样例解释 2

$t_3 \ge t_1 + 9$t​3​​≥t​1​​+9，$t_1 \ge t_3 -1$t​1​​≥t​3​​−1，合并以后得到 $t_1 \ge t_1 + 8$t​1​​≥t​1​​+8，不可能满足客人们的所有要求。

样例输入1

3
5
2 3 2 10
2 2 1 2
2 3 2 5
1 2 3 7
3 3 9

样例输出1

12

样例输入2

3
4
3 1 3
2 3 1 9
2 1 3 -1
1 1 2 5

样例输出2

I can't

样例输入3

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

样例输出3

77