首先容易得到一些性质：首先把所有打算用 AI 的一起放在所有手写前面不劣，且根据 exchange arugment 有 AI 之间是按照 $B_i$ 升序排序的，所以其实只要觉得哪些任务用 AI，倒数第 $k$ 个 AI 的代价是 $kB_i$。

然后就可以 DP 了，初始默然全手写，代价为 $\sum A_i$，按照 $B_i$ 降序处理，设 $f(k)$ 表示当前选了 $k$ 个 AI，转移为 $f'(k)=\min(f(k), f(k-1)+kB_i-A_i)$。现在可以做到 $\mathcal{O}(n^2)$。

根据一些说法，不妨先假设这个东西是凸的。考察差分，$d_k=f(k)-f(k-1)$，那么 $kB_i-A_i$ 更优等价于 $d_k-kB_i>A_i$，我们可以在后续归纳说明 $d_{k+1}-d_{k}\ge B_i$，所以 $d_k-kB_i$ 单调不降，只需要找到第一个 $d_k-kB_i$ 不降的位置，用二分和平衡树维护 $d_i$ 即可做到 $\mathcal{O}(n\log n)$。

上面结论的证明：考虑归纳，由于 $B_i$ 不降，若 $d_{k+1}-d_k\ge B_{i-1}$，我们自然有结论成立，于是只要证 $d_{k+1}'-d_k'\ge B_i$，由于 $d'$ 相当于一个单点插入和后缀加，列一下有变化的地方就发现不会出现问题。

但是上面的东西看上去不太好想到，这个 $d_{k+1}-d_k\ge B_i$ 是一个比凸性更强的性质，转移中比较不同的地方就是 $kB_i$ 这一项，如果没有这一项，就是 $f$ 和 $[0,-A_i]$ 这个序列的闵可夫斯基和，显然是凸的。令 $a=A_i,b=B_i$，这个形式就是 $f'(k)=\min(f(k),f(k-1)-a)$。对于有 $kb$ 的情况，我们考虑构造一个 $g(k)=f(k)+h(k)$ 使得 $g'(k)=\min(g(k),g(k-1)-a)$。那么有 $f'(k)=\min(f(k),f(k-1)+h(k-1)-h(k)-a)$，于是我们要求 $h(k-1)-h(k)=kb$，那么 $h(k)=-b\binom{k+1}2$，所以其实 $f$ 的二阶差分 $\ge b$ 等价于 $g$ 是凸的。当 $b$ 减小时，$g(k)$ 会加上凸函数 $\binom{k+1}2$ 的正数倍，所以仍然是凸的。于是 $f$ 的二阶差分始终 $\ge b$，或者你直接维护 $g$ 的差分也是没问题的，每次转移是插入一个 $-a$。这里的思路是什么？$kb$ 这一项比较讨厌，我们尝试通过一些转化把它变为常见的形式，进而说明凸性甚至一个更强的性质。思路来源：jiangly。