鬼知道怎么会撞题的，甚至是没听过的 OJ。
首先不考虑对 \(a_i\) 取 \(\max\)，显然直接按照 \(k\) 降序排序最优。
接下来考虑 \(a_i\) 的限制，如果取到了 \(a_i\) 一定放在最后面最优。
为了方便设 \(f_{i,j}\) 为前 \(i\) 个，\(j\) 个数字不取 \(\max\)，最后答案和 \(\sum b\) 的差的最小值。
设 \(lim_i=b_i-a_i\)
这样时间复杂度为 \(\Theta\left(n^2\right)\)、
考虑优化。
首先对于样例输出一个整个 \(f\)。
我们发现对于给定的 \(i\)，在 \(j\) 改变的时候是下凸的，可以使用 slope trick。
对 \(j\) 一维差分，设 \(g_{i,j}=f_{i,j}-f_{i,j-1}(j>0)\)。
默认 \(1<j<i\)，将 \(f_{i,j}=f_{i,0}+\sum\limits_{k=1}^jg_{i,k}\) 带入 \(f_{i,j}\) 的递推式。
得到
\[f_{i,0}+\sum_{k=1}^{j}g_{i,k}=\min\{f_{i-1,0},\sum_{k=1}^{j}g_{i-1,k}+lim_i,f_{i-1,0}+\sum_{k=1}^{j-1}g_{i-1,k}+k_i\times j\} \]化简得
\[lim_i+\sum_{k=1}^{j}g_{i,k}=\sum_{k=1}^{j-1}g_{i-1,k}+\min\{g_{i-1,j}+lim_i,k_i\times j\} \]对于上式用 \(j-1\) 代替 \(j\)
\[lim_i+\sum_{k=1}^{j-1}g_{i,k}=\sum_{k=1}^{j-2}g_{i-1,k}+\min\{g_{i-1,j-1}+lim_i,k_i\times (j-1)\} \]两式相减，得到
\[g_{i,j}=g_{i-1,j-1}+\min\{g_{i-1,j}+lim_i,k_i\times j\}-\min\{g_{i-1,j-1}+lim_i,k_i\times (j-1)\} \]令
\[F_i(j)=g_{i-1,j}+lim_i-k_i\times j \]由于 \(k\) 单调不增，因此可以使用数学归纳法证明，对于自变量 \(j\)，\(g_{i-1,j}\) 的增长速度比 \(k_i\times j\) 快，所以 \(F_i(j)\) 随着 \(j\) 的增大，先负后正。
因此，从 \(g_i\) 到 \(g_{i+1}\)，一段不变，中间多一个数，一段加上一个数，当然可能头尾两端可能为空。
用平衡树维护，\(O(n\log n)\)