§0x00 题意
给你 $N$ 序列，第 $i$ 个的长度为 $M_i$，要求在每个序列中选择一个数，每种选法的代价为选择的 $N$ 个数之和，请求出代价前 $K$ 小的方案。
$N,K\leq10^5,M_i\leq10$
§0x01 暴力
容易得出两个结论：
-
每个序列要从小到大选；
-
最小解为每个序列最小值之和。
于是就有了一个及其暴力的写法：
首先将所有序列从小到大排序，然后维护小根堆。
一开始将最小解（也就是所有序列选第一个数）入堆，
之后 $K$ 次出当前堆中最小的数，考虑将这个状态扩展，
对于这个状态将他的后继状态入堆，也就是从 $1$ 到 $N$ 枚举哪一行往后多选一个，将这 $N$ 后继种状态入堆。
这个算法的正确性很容易保证，问题是效率太低，每次扩展都要枚举 $N$ 种情况。
时间复杂度 $O(nk)$；
空间复杂度 $O(nk)$，因为堆中需要有至少 $N$ 个状态，每个状态需要记录 $N$ 行的情况。
§0x02 优化1
考虑优化上述暴力。
为了方便，接下来我要用图片来表示每一种状态：
这个图片为 $N=3,M_i=5$ 的情况 ，
左侧一列灰色格子，表示每个序列的最小值，
每行加重的颜色，代表着这个序列选的数，上图代表着第一行选了第 $4$ 小的数，第二行选了第 $3$ 小的数，第三行第 $5$ 小。
回到我们的暴力，我们发现，每个状态会被不止一个前驱状态入堆。
下面这三个货均会让上面的入堆。
但是，只要任意一个前驱状态入堆，就可以保证这个情况被考虑。
减少每个状态的前驱状态，是我们优化的核心。
现在，我们规定，每个状态的前驱状态，就是这个状态的最后一行选择前一个数的状态（这个数一定比当前的小）。
特殊的，如果最后一行已经选了最小的无法再小，那就从下往上选择第一个可以更小的行（这行选的数一定是第二个或者更往后）。
举例（上面是下面的前驱状态）：
注意到，每个状态的前驱状态的代价都比自己小，这就代表着每个状态都打好提前量，在合适的时候入堆，不会出现错误。
到目前，我们已经保证每个状态都用唯一的前驱状态，那么，是不是每个状态都有一个后继状态呢？
我们考虑下面这个状态的后继状态，相当于考虑哪些状态会将下面这个状态称为前驱状态。
首先，是将最后一行（蓝色行）往后选一个的情况，这种情况的前驱一定当前状态。
但是假设蓝色行后面有一行选了第二个数，那么变为最小值之后，其前驱也是当前状态，下面这两种也是其后继。
那到这就有点难办了，一个状态最多有 $N$ 个后继，这不和没优化一样嘛！
§0x03 优化2
我们的困难是，一个状态可能有若干个后继状态，但我们发现，这若干个状态有一个共同点。
除了那个将最后一行再选一个的一般情况，剩下的后继状态，都是要将下面一个选最小的行选第 $2$ 个。
我们考虑，这些状态一定需要同时入堆吗，这些状态有没有所谓的前驱、后继关系呢？
我们要知道，前驱后继的关键所在，就是某个值一定比另一个值小，只有这样，后继才能在前驱后入堆。
那么，我们要增加的第二列，有一个大小关系吗？
我们将后两行的前两个标上数试试。
那么我们两个后继中，将第 $3$ 行选第 $2$ 个增加的代价为 $4-2$，将第 $4$ 行选第 $2$ 个增加的代价为 $5-4$，显然后者更小。
那么，我们：
-
将「第 $3$ 行选第 $2$ 个，第 $4$ 行选第 $1$ 个」设为「第 $3$ 行选第 $1$ 个，第 $4$ 行选第 $2$ 个」的后继；
-
将「第 $4$ 行选第 $2$ 个」设为「当前状态」的后继。
但我们发现这样的顺序很难维护，所以我们先将所有行的 $f_{i,2}-f_{i,1}$ 从小到大排序。
这样，我们每个状态的后继都可以很清楚的表达出来了：
- 当前行，选择下一个；
- 下一行，选择第二个；
- 如果当前行正在选第二个，则还可以变为「当前行选择第一个，下一行选择第二个」。
这样，每个状态只有 $3$ 个后继了，时间复杂度为 $O(k\times\log{n})$，可以接受.
但是如果每个状态都把每一行选到第几列记录的话，空间复杂度 $O(n^2)$ 就难以接受了。
但考虑到，如果现在最后一行为 $i$ 的话，后继状态是不会改变 $1$ 至 $i-1$ 行的，所以我们只要记录当前行以及这行选了第几个即可。
§0x03 code
一些小提示：
- 状态不能用 set 去重~~（画蛇添足~~，因为理论上已经不可能重复加入，由于状态只记录了最后一行选的数，不保证前面行所取的完全一样，去重会少情况；
- 用查分更好实现，但在这里方便理解我没用，读者可以自行尝试；
- 需要 long long；
代码：
|
|