钢铁之躯

Time Limit: 1000MS

Memory Limit: 131072KB

Description

通过追寻超人无意间发出的氪星讯号,邪恶的Zod将军带领他的军队跨越了漫长的光年,抵达了地球。在漫长的太空旅行中,Zod在氪星人以前探索过的的星球上,搜集了了n个氪星改造器,他将这些改造器带到了地球,试图摧毁地球重建氪星。

正义的超人当然不能允许邪恶的Zod将军摧毁地球,为了摧毁Zod将军散布在世界各地的并派遣重兵把守的氪星改造器,超人需要吸收阳光补充能量。已知超人储存阳光的能量不能大于一个上限m,同时地球各地的光照条件不一样,所以吸收同等的阳光所花费的时间也不一样,超人必须按照顺序摧毁改造器解救地球,问他最少需要多少时间?

Input


第一个是样例数t(t<=60),每个样例首先是两个数字n,m,代表超人需要摧毁的氪星改造器的数目n,还有他所能最大储存的太阳能量m,接下来是n行,分别有两个数字x,y,代表摧毁第i个氪星改造器的所需消耗的能量x,以及在第i个氪星改造器所在地吸收单位能量所需花费的时间y,超人必须按照从1到n的顺序摧毁改造器,如果超人在能量不够,则因无法摧毁改造器而战死,除t之外的数字大于0不超过100000.


Output

如果能摧毁所有的改造器,输出最少需要多长时间(只算吸收阳光的时间,战斗时间忽略不计),如果超人不能摧毁所有的改造器,输出"superman is dead!".


Sample Input

3
3 10
10 5
5 10
2 10
2 20
22 1
10 10
3 5
1 10
2 8
3 5

Sample Output

120
superman is dead!
41

Hint

超人初始能量为0,超人在战斗前吸收阳光,战斗结束后立刻去到下一个地点。

Source

None

提交代码