P12149 【MX-X11-T3】「蓬莱人形 Round 1」科学

原题链接：。 --- 「少しの眠れぬ夜に」 「この魔法がほのかに灯るなら」 「今がそんなに悪くないって」 「笑える時まで今日もscience!」

初始你有 $n$ 个 A 类盒子，第 $i$ 个盒子里有 $a_i$ 个颜色为 $i$ 的球，且每个 A 类盒子的大小无限制。还有 $m$ 个 B 类盒子，购买第 $i$ 个 B 类盒子的花费为 $w_i$，且有大小上限 $b_i$。 你可以进行任意次操作，每次选择一个盒子里的一个球，把它放到另一个盒子中，但你要保证**最终**： - 每个盒子中的球颜色相同。 - 存在序列长度为 $n$ 的盒子序列 $p$（即**盒子 $p_i$ 可以表示任意一个 A 类或 B 类盒子**），满足对于所有 $i\in[1,n]$，颜色为 $i$ 的小球只会出现在第 $i$ 个 A 类盒子或**盒子 $p_i$**。 你要购买若干个 B 类盒子后（可以不购买）进行上述操作使得所有盒子中球的数量的**最大值最小**，并且**在此基础上**最小化购买 B 类盒子的总花费。 **若未特别标注，则「盒子」表示「A 类盒子」与「B 类盒子」的总称。**

无

无

**【样例解释 #1】** 买第 $1$ 个 B 类盒子 $(3,3)$，并将第 $1$ 个 A 类盒子中的 $2$ 个颜色为 $1$ 的球放到这个 B 类盒子中即可，花费为 $3$。 **【样例解释 #2】** 买第 $1$ 个 B 类盒子 $(5,2)$ 和第 $4$ 个 B 类盒子 $(1,5)$，并将第 $1$ 个 A 类盒子中的 $1$ 个颜色为 $1$ 的球放到第 $4$ 个 B 类盒子，将第 $3$ 个 A 类盒子中的 $3$ 个颜色为 $3$ 的球放到第 $1$ 个 A 类盒子，将第 $5$ 个 A 类盒子中的 $3$ 个颜色为 $5$ 的球放到第 $1$ 个 B 类盒子，所有盒子球数最大值为 $4$，花费为 $7$。 **【数据范围】** **本题使用子任务捆绑**。 对于所有测试数据，$1 \le n,m \le 2 \times 10^5$，$1\le a_i,b_i,w_i \le 10^9$。 |子任务编号|$n\le$|$m \le$|特殊性质|分值| |:-:|:-:|:-:|:-:|:-:| |$1$|$6$|$6$|无|$10$| |$2$|$2 \times 10^5$|$1$|无|$15$| |$3$|$2 \times 10^5$|$5$|无|$20$| |$4$|$2 \times 10^5$|$2 \times 10^5$|保证所有 $a_i,b_i \le 2$|$15$| |$5$|$2 \times 10^5$|$2 \times 10^5$|无|$40$|