陶陶玩红警
测试数据来自 system/1679
背景
陶文博最近开始玩红警了。。。
描述
陶陶玩的是twb版红警,这个版本的红警是这样的:一开始你就有一个战车工厂。接下来,在任意一秒内,你可以选择建造一个战车工厂,或者让当前所有的战车工厂各造出一辆犀牛坦克,如果当前有k个战车工厂,则这一秒内能造出k个犀牛坦克。(造坦克和造战车工厂不能同时进行)
陶陶在玩了1个月红警之后,认为自己红警很厉害了,于是向curimit发了一份挑战书,陶陶还嚣张地说他会对curimit发动n次攻击,第i次攻击在time[i]秒末,会使用number[i]辆犀牛坦克来进攻,消灭掉curimit家里同等数量的犀牛坦克,如果此时curimit家里没有这么多的犀牛坦克的话,curimit就死翘翘了。
curimit接到了这份战书后,看到陶陶如此强大的攻势,被吓得不轻。他想请你帮帮忙,帮他制定一份作战计划(什么时候造战车工厂,什么时候造坦克):curimit希望在抵挡了之前陶陶的进攻之后,在第final秒末发动最终总攻击,一举歼灭陶陶的老家。他希望你的作战计划能够在第final秒末造出最多数量的坦克。
格式
输入格式
输入文件的第一行为两个整数n,final分别表示陶陶一共发动n次攻击,curimit的总攻击时间是第final秒末。
第2行开始到第n+1行,第i+1行有两个数time[i]和number[i],表示陶陶将在第time[i]秒末使用number[i]辆犀牛坦克,向curimit发起进攻。
输出格式
输出文件仅包含一行,如果curimit无法抵挡陶陶的进攻,那么输出"twbzuobile";否则输出第final秒末curimit最多能拥有多少辆坦克。
样例1
样例输入1
3 10
5 3
7 13
9 4
样例输出1
8
限制
4秒
提示
【样例解释】
第1秒:造战车工厂。
第2秒:造战车工厂。
第3秒:造战车工厂。
第4秒:造坦克,当前坦克数:4。
第5秒:造坦克,当前坦克数:8.
第5秒:陶陶带了3辆坦克冲了进来,当前坦克数:5
第6秒:造坦克,当前坦克数:9。
第7秒:造坦克,当前坦克数:13。
第7秒:陶陶带了13辆坦克冲了进来,当前坦克数:0
第8秒:造坦克,当前坦克数:4。
第9秒:造坦克,当前坦克数:8。
第9秒:陶陶带了4辆坦克冲了进来,当前坦克数:4。
第10秒:造坦克,当前坦克数:8。
在第final秒末,curimit家里最多有8辆坦克。
【约定】
对于10%的数据, n≤4 final≤10
对于30%的数据, n≤1000 final≤1000
对于100%的数据,n≤100000 final≤10^8
来源
原创题。