先将数组按照 aa 从小到大排序（注意 bb 的顺序要跟随 aa 变化）。

考虑选择 11 个数 aiai​，令其为 max⁡max，为了使这种情况下乘积最小，我们需要使选择的另外 k−1k−1 个数的 bb 的和最小。于是我们需要选择前 k−1k−1 小的 bjbj​，前提是选择的数的 aa 值都小于 aiai​，不然 aiai​ 就不是 max⁡max 了。而我们刚刚已经按照 aa 排序了，所以只需要在下标小于 ii 的数中选择前 k−1k−1 小的 bb 就可以满足前提。

整理一下思路：排序，从前往后枚举 ii，设数组 bb 中下标小于 ii 的前 k−1k−1 小的数的和为 sumsum，统计答案，即 ans=min⁡(ans,ai×(sum+bi))ans=min(ans,ai​×(sum+bi​))，最后输出 ansans 即可。

现在的问题是如何快速求出 sumsum。

首先，我们不需要每枚举到一个 ii，就将 b1b1​ 到 bi−1bi−1​ 重新排序。而是每枚举到一个 ii，在 i−1i−1 的结果上做微操，得到 ii 的结果（这个思路在 abc 中经常用到）。

我们思考 sumsum 的含义，是：数组 bb 中下标小于 ii 的前 k−1k−1 小的数的和（下面记 sumisumi​ 为枚举到 ii 时的 sumsum 值）。

假设我们现在已经知道了 sumi−1sumi−1​，那么我们应该判断 bibi​ 与下标小于 i−1i−1 的 bb 中第 k−1k−1 小的数（记为 ti−1ti−1​）的大小关系，如果 bi≥ti−1bi​≥ti−1​，那么 bibi​ 就不会使前 k−1k−1 小的数发生变化，于是 sumi=sumi−1sumi​=sumi−1​；如果 bi<ti−1bi​<ti−1​，那么 bibi​ 就会成为前 k−1k−1 小的数之一，而 ti−1ti−1​ 就不在前 k−1k−1 小的数当中了，于是 sumi=sumi−1−ti−1+bisumi​=sumi−1​−ti−1​+bi​。

所以我们现在就是要维护 titi​，这固然可以用对顶堆，但是本蒟蒻赛时没想到，用了平衡树（雾）。

最后一个问题：如何求出初始的 sumsum？实际上很简单，显然 ii 是要从 kk 开始的，而这时 ii 前面有且仅有 k−1k−1 个元素，因此这 k−1k−1 个元素一定是前 k−1k−1 小的。

代码较长，请在 https://www.luogu.com/paste/ytbmfrzj 中查看。