TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4264
  • 题目
  • P4264蒜头君当大厨
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

    蒜头君苦练厨艺,终于成为了某高档酒店的大厨。 每天上班,蒜头君会被要求做 nnn 份菜。既然是高档酒店,那么客人们当然是很讲究的,尤其对于上菜的时间有很多要求。客人们的要求被分成下列四种:
    菜品 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。

    样例输入 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

    提示

    对于 30%的数据:1≤n≤4,1≤m≤10,0≤∣d∣≤10。

    对于 60% 的数据:1≤n≤1000,并且输入保证有解。

    【样例说明 1

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

    样例说明 2

    t3≥t1+9,t1≥t3−1,合并以后得到 t1≥t1+8,不可能满足客人们的所有要求。

    对于 100%的数据:1≤n,m≤20000,1≤∣d∣≤10000,1≤a,b≤n,a≠b。


    来源  计蒜客17294