路线安排

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

今天上午第一节就有课,小豪却睡迟了。等到他起床的时候,离上课还有t分钟从寝室到教室的远远大于t分钟,如果直接走的话,看起来小豪是一定要迟到了。然而机智的小豪在平时生活中记着一些近路如果抄近路还是会迟到的话,小豪就不去上课了。不过因为时间比较紧,小豪在匆忙中只记得的有哪些近道忘记怎么走才能花费最少的时间。聪明的你能帮他解决这个问题吗
小豪寝室到教室的一种可能的路线如图所示

小豪寝室到教室的路线两条主干道,每一天主干道上都有n个三岔路口,小豪到每一路口的时候都可以选择换线或者不换,如果换线的话需要额外的抄近道的时间
上图最优的路线为 寝室->A1->A2->B2->B3->B4->教室

Input

多组输入( 约10组),处理到文件结束(EOF)
每组数据第一行为两个整数,分别为n,t(0 < = n < = 1000000,0 < = t < = 100000000)
然后一行n+1个数,代表第一条主干道上的各段路需要花费的时间
接下来一行n个数,i个数代表Ai到Bi需要花费的时间
接下来一行有n+1个数,代表条主干道上的各段路需要花费的时间
保证每条路上花费的时间不超过100

Output

如果小豪不可能在t分钟内到达教室,输出“Sleep Again!”(不包括引号
否则的话输出小豪到教室之后能剩余的最多时间

Sample Input

4 130
50 5 40 10 20 
30 20 25 8
30 90 1 8 20
1 5
30 20
30
20 10
1 20
10 10
30
10 20

Sample Output

26
Sleep Again!
0

Hint

 

Source

QAsQ