bzoj#P2041. [2009国家集训队]陶陶玩红警

[2009国家集训队]陶陶玩红警

题目描述

陶陶最近开始玩红警了,他玩的是自己 MOD 的一个红警版本。这个版本是这样的:你只能造两样东西,战车工厂和坦克。最初你有一个战车工厂,然后在接下来的每一秒内你可以有两种选择(假设当前有 kk 个战车工厂):

  1. 建造一个战车工厂;
  2. 建造 kk 辆坦克。

注意,战车工厂和坦克是不能同时建造的。陶陶在玩了一个月红警后,认为自己红警水平很厉害了。于是他向 curimit 发了一份挑战书,他还嚣张地说他会对 curimit 发动 NN 次攻击。第 ii 次攻击在第 timeitime_i 秒末,陶陶会使用 numinum_i 辆坦克来进攻,消灭掉 curimit 家里同等数量的坦克。如果此时 curimit 家里没有这么多的坦克的话,那么 curimit 就死翘翘了。curimit 接到战书后看到看到陶陶如此强大的攻势,被吓得不轻。他想请你帮帮忙,帮他制定一份作战计划(什么时候造战车工厂,什么时候造坦克):curimit 希望在抵挡了陶陶的 NN 轮进攻之后,在第 finalfinal 秒末发动最终的总攻击,一举歼灭陶陶的老家。他希望你的作战计划能够在第 finalfinal 秒末造出最多数量的坦克。

输入格式

11 行为两个整数 N,finalN,final,含义如题目中所述。
接下来 NN 行,第 ii 行有两个数 timeitime_inuminum_i,含义如题目中所述。

输出格式

如果 curimit 无法抵挡陶陶的进攻,那么输出 No Answer!;否则输出第 finalfinal 秒末 curimit 最多能拥有多少辆坦克。

样例输入

3 10
5 3
7 13
9 4

样例输入

8

样例说明

11 秒:造战车工厂。
22 秒:造战车工厂。
33 秒:造战车工厂。
44 秒:造坦克,当前坦克数:44
55 秒:造坦克,当前坦克数:88
55 秒:陶陶带了 33 辆坦克冲了进来,当前坦克数:55
66 秒:造坦克,当前坦克数:99
77 秒:造坦克,当前坦克数:1313
77 秒:陶陶带了 1313 辆坦克冲了进来,当前坦克数:00
88 秒:造坦克,当前坦克数:44
99 秒:造坦克,当前坦克数:88
99 秒:陶陶带了 44 辆坦克冲了进来,当前坦克数:44
1010 秒:造坦克,当前坦克数:88
在第 10 秒末,curimit 家里最多有 88 辆坦克。

数据规模与约定

对于 10%10\% 的数据,N5N \leq 5final10final \leq 10
对于 30%30\% 的数据,N103N \leq 10^3final103final \leq 10^3
对于 100%100\% 的数据,N105N \leq 10^5final109final \leq 10^90numi10180 \leq num_i \leq 10^{18}1timei1 \leq time_i

题目来源

版权所有者:宋文杰