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

    ID: 1064 传统题 1000ms 259MiB 尝试: 23 已通过: 9 难度: 9 上传者: 标签>CF2700省选/NOI-线性 DP交换论证分段多项式二分查找凸性/单峰性判定事件排序版权所有者:宋文杰

[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_i 和 numinum_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\% 的数据,N≤5N \leq 5,final≤10final \leq 10。
对于 30%30\% 的数据,N≤103N \leq 10^3,final≤103final \leq 10^3。
对于 100%100\% 的数据,N≤105N \leq 10^5,final≤109final \leq 10^9,0≤numi≤10180 \leq num_i \leq 10^{18},1≤timei1 \leq time_i。

题目来源

版权所有者:宋文杰