• [B] Mr. Cai Saves TT

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Long long ago, a princess called TT. She was catch by dragon. Mr.Cai is go to save TT.

    Mr.Cai should through a channel. The channel's length is l.

    Every second Mr. Cai can go on step. And Mr. Cai have super powers that he can go c step in one second but after he use this power he go to a special place to get his power back. before that he can't use this powers.

    In the channel, there are n special places. di means where the ith special places is. bi means how much time Mr. Cai should stay in the ith special places to get his power back.

    Now Mr. Cai is going to save TT. He must arrive in t second. If he can do this TT will eaten by dragon.
  • 输入
  • The first line will input four integers l, t, n, c.
    Then following n lines each line contain two integers di, bi.(0< di <l) if i < j, di < dj.
    0 < n < l < 1010.
    0 < t < l.
    0 < c <= 20.
  • 输出
  • For each case, you should output one line.
    If Mr.Cai can save the TT, print "Mr. Cai can save TT in n seconds".
    Otherwise print "Sorry TT be eaten by dragon".
  • 样例输入
  • 10 4 1 4
    4 1
    10 4 1 5
    4 1
  • 样例输出
  • Sorry TT be eaten by dragon
    Mr. Cai can save TT in 4 seconds
  • 提示
  • 来源
  • Lucifer
  • 操作

显示春菜