开局先令 $h_i\gets h_i-1$，然后按攻击力 $a$ 对怪兽排序。

容易发现一件事：若当前我们持有的剑最大攻击力为 $a_p$，则对于某个没打的怪兽 $i$ 且 $a_i\le a_p$，我们没有必要先去打 $i$，完全可以等持有 $a_p'\ge a_n$ 的时候再去打 $i$，于是我们可以设 $f_i$ 表示从排序过后的第一个怪兽开始，截至到 $i$ 且必须打 $i$ 的最小 $H_0$，显然目前的 $a_p=a_i$，先把全部数的贡献 $\lfloor\frac{h_i}{a_n}\rfloor\times a_i$ 给加上，然后 dp 就是 $f_j\gets\min_{i<j}f_i+(\lfloor\frac{h_j}{a_i}\rfloor-\lfloor\frac{h_j}{a_n}\rfloor)\times a_j$，做到 $O(n^2)$。

考虑优化。我们要处理的麻烦项是 $f_i+\lfloor\frac{h_j}{a_i}\rfloor\times a_j$，注意到 $a_i=a_j$ 的转移不优所以我们可以把所有 $a_i=a_j$ 的 dp 值更新完了再转移 $a_i<a_k$，直接枚举 $a_i$ 的倍数，是调和级数复杂度 $O(n\ln n)$，因为我们是一起转移所以每个不同的 $a_i$ 只被遍历 1 次，然后就变成 $f_i+k\times a_j$ 的形式，注意到是个一次函数，我们直接放线段树上，显然只有凸包上的点是有用的，同时 $a_i$ 不降所以对于每个 $x$ 满足 $\lfloor\frac{x}{a_i}\rfloor$ 不升，也就是我们加入的斜率是不升的，容易拿单调栈维护凸包，由于我们总共加入 $O(n\ln n)$ 个区间，所以这里的时间复杂度是 $O(n\ln n\log n)$，空间是 $O(n(\ln n+\log n))$ 的。对于查询的话就是看单点到线段树根上的 $O(\log n)$ 个凸包带点求值，一次查询加上二分做到 $O(\log^2n)$。

注意点：特判 $a_0=\max a$ 的情况，对于相同的 $a_i$ 我们等 dp 值更新完后一起转移，准确来讲是取 $f_i$ 最小的转移，取 $h_i$ 最小的是错误的，给出一组样例：

2 2
5 5
5 6