\(Part\ 0:\)我瞎扯扯

我做这题时想着先把耗费魔法值为负的做掉，然后最后再做一段魔法值为正的，但是不好做，做不了。

这个东西也贪心不了，因为你魔法值和伤害这两个东西拆不开，然后就什么都做不了了。

~~本篇题解中没有什么心路历程，又不能分析出什么动机，因为笔者纯菜，就当看乐子就完了~~

\(Part\ 1:\)正解

我们为了方便把 \(C\) 的符号都给反转，正的变负的，负的变正的。然后我们再记 \(L=300\) 即 \(C\) 的最大绝对值。

\(Part\ 1.1:\) 初步性质探究

我们考虑怎样的操作序列是合法的，那么就是对于任何 \(j\) ， \(\sum\limits_{i=1}^j C_i\ge 0\) ，否则不合法性是显然的。我们称满足这个条件的操作序列为 \(\color{red}\text{合法操作序列}\)

我们考虑再记一个定义，一个操作序列中，对于任何 \(j\) ，满足 \(\sum\limits_{i=1}^j C_i\le 2L\) 那么我们这个操作序列为 \(\color{red}\text{优秀操作序列}\)

对于优秀操作序列有着极好的性质，因为他满足任意 \(C\) 的前缀和都小于 \(2L=600\) ，也就是说我们能够用一个背包的维度去存储，不过暂时先不管这个。

为了方便，我们记 \(sum_i\) 表示 \(C\) 数组前 \(i\) 项的和。

引理 \(1\)

任何合法操作序列都可以拆分成若干个优秀操作序列，且满足长度和造成的伤害相等

证明：

这个正确性是比较显然的，考虑如果存在一个 \(i\) 满足 \(sum_i>2L\) ，那么我们可以从后面移动一些 \(C_i<0\) 的东西放到他前面，直到满足他前面的数的和 \(\le L\) ，那么这时候把这个数放进去是一定不会超限（因为每个数 \(\le L\) ）。我们记最后一个 \(C_i<0\) 的位置为 \(q\) ，那么 \(q\) 和他前面的数构成一个优秀操作序列，由于 \(q\) 后面的数每个都是正数，且没有负数去拼了，可以把每个正数都看成一个长度为 \(1\) 的优秀操作序列。

举个例子，最终 \(C\) 的值是 \(0,1,-1,3,1,-2,1,2,1\) ，那么 \(0,1,-1,3,1,-2\) 构成一个优秀操作序列， \(1,2,1\) 各自构成一个优秀操作序列。

知道了合法操作序列的一些性质之后，我们来研究优秀操作序列的性质。

引理 \(2\)

任何极小优秀操作序列的长度是0~2L的

证明：

这个可以根据鸽巢原理得到，倘若某个极小优秀操作序列长度是 \(2L\) 。那么我们根据优秀操作序列的性质， \(sum\) 的取值至多只有 \(2L\) （不算 \(0\) ）个，那么倘若有 \(2L+1\) 个，那么一定存在某个地方满足 \(sum_i=sum_j(i\not =j)\) ，我们钦定 \(i<j\) ，那么 \(i+1\sim j\) 这一段数就可以用另一个优秀操作序列来表示，这个也是显然的。

\(Part\ 1.2:\) 问题转化

我们称既合法又优秀的操作序列为合法优秀操作序列。

我们现在任何的一个合法操作序列都可以拆分成若干个长度在 \(0\sim 2L\) 之间的极小合法优秀操作序列。

那么实际上我们最终答案就是这些极小合法优秀操作序列拼起来的。

我们考虑对于每个长度的操作序列求一个最优值（伤害最高），记为 \(D_i\) ，表示长度为 \(i\) 的极小合法优秀操作序列能造成的最大伤害是多少。

那么现在问题就变成了，我们有 \(0\sim 2L\) 这些连招，问我们如何释放连招，才能使得杀死 \(monster\) 的耗费步数最少。

\(Part\ 1.3:\) 进一步挖掘性质

这时候其实我们根据直觉肯定是先用一个性价比最高的连招然后打了很多很多次，然后最后余下一些生命值再考虑用其他连招去打，可能更优。

我们考虑反过来先用其他连招打，再用性价比最高连招打。

如果直接选显然是做不了的，我们只能挖掘一些性质。

引理 \(3\)

非性价比最高的连招至多使用2L次

证明：

我们先把非性价比最高的连招放在最前面，假设有 \(2L+1\) 。\(w_1,w_2...,w_{2L+1}\) 每个 \(w\) 代表一个连招。我们记 \(s_i\) 为前 \(i\) 个连招的操作序列的长度和（即为总操作次数）。

然后记 \(z\) 为性价比最高的连招的长度。那么 \(z\) 最大为 \(2L\) ，所以根据鸽巢原理，如果用了 \(2L+1\) 个非性价比最高连招，一定会出现某个 \(s_i\equiv s_j(mod\ z)(i\not =j)\) ，这一段一定可以用我们的最优性价比连招平替，证毕。

\(Part\ 1.4:\)解决问题

由于非性价比最高连招至多用 \(2L\) 个，所以总长度至多为 \((2L)^2\)

记 \(g_i\) 为总长度为 \(i\) 的操作序列最多能造成多少伤害。

然后我们枚举 \(i\) ，用 \(H-g_i\) ，然后用最优性价比的连招去看一下要打多少次即可。

计算 \(D\) 的复杂度是 \(O((2L)^2n)\) ，计算 \(g\) 的复杂度是 \(O((2L)^2L)\)

总复杂度 \(O(4L^3)\)

\(Part\ 2:\) 简要总结做法（省流）

每个优秀操作序列可以转化成若干个优秀操作序列，每个极小优秀操作序列长度小于等于 \(2L\) 。

然后我们获得了 \(2L\) 中连招，又发现非性价比最高连招最多使用 \(2L\) 次，然后就算出使用 \(i\) 次的最优值，然后枚举即可。

\(Part\ 3:\) 启示

这题的难点在于需要我们不断去挖掘性质，通过证明来获得结论，将题目转化成一个比较简单的模型。

~~但是这有用什么用呢，毕竟找性质的能力不是说说就能有的~~

\(talk\ is\ cheap,show\ me\ your\ code:\)

点击查看代码

#include<bits/stdc++.h>
typedef long long LL;

using namespace std;
const LL MAXN=310;
LL n,H,L=300;
struct ddl {
	LL c,d;
}a[MAXN];
LL f[MAXN<<1][MAXN<<1];//选了i个数，C值为j的最大伤害
LL D[MAXN<<1];//长度为i的极小合法优秀操作序列能造成的最大伤害
LL g[(MAXN*MAXN)<<2];//长度为i的，有若干个连招构成的操作序列造成的最大伤害。
int main () {
	scanf("%lld%lld",&n,&H);
	for(int i=1;i<=n;++i) {
		scanf("%lld%lld",&a[i].c,&a[i].d);
		a[i].c=-a[i].c;
	}
	memset(f,128,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=2*L;++i) {
		for(int j=0;j<=2*L;++j) {
			for(int q=1;q<=n;++q) {
				int t=j-a[q].c;
				if(t>=0&&t<=2*L&&f[i-1][t]>=0)
				f[i][j]=max(f[i][j],f[i-1][t]+a[q].d);
			}
		}
	}
	double da=0;
	LL key;
	for(int i=1;i<=2*L;++i) {
		for(int j=0;j<=2*L;++j) {
			D[i]=max(D[i],f[i][j]);
		}
		if(D[i]*1.0/i>da) {
			da=D[i]*1.0/i;
			key=i;
		}
	}
	memset(g,128,sizeof(g));
	g[0]=0; 
	for(int i=0;i<=2*L*2*L;++i) {
		for(int j=0;j<=min(2*L,(LL)i);++j) {
			g[i]=max(g[i],g[i-j]+D[j]);
		}
	}
	LL ans=1e18;
	for(int i=0;i<=2*L*2*L;++i) {
		LL res=max(0ll,H-g[i]);
		LL ls=i;
		if(res%D[key]) {
			ls=(ls+(res/D[key]+1)*key);
		}
		else {
			ls=(ls+(res/D[key])*key);
		}
		ans=min(ans,ls);
	}
	printf("%lld\n",ans);
	return 0;
}