/ Vijos / 题库 /

陶陶玩红警

陶陶玩红警

背景

陶文博最近开始玩红警了。。。

描述

陶陶玩的是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

来源

原创题。