题目
问题描述
小D一觉醒来，惊讶地发现试题纸背面还有一题。
- 给出$N$个数$A_i$。
- 求一个$1 \sim N$的排列$P$，最小化$\sum_{i= 1}^{N}A_iP_i$。
这看上去是一道普及组题，但无趣的出题人打算让选手求出前$k$优解。
假如两个排列$P, P’$中，存在至少一个$i \in [1, N]$满足$P_i != P’_i$，那么排列$P, P’$被认为是不同的。
现在你需要求出前$k$优解中$\sum_{i= 1}^{N}A_iP_i$的值。
输入格式
从文件water.in中读入数据。
第一行，两个正整数$N, k$。
接下来$N$行，每行一个整数$A_i$。
输出格式
输出到文件water.out中。
依次输出$k$行，表示前$k$优解的值。
样例输入1
3 5
2
3
3
样例输出1
15
15
16
16
17
样例输入2
6 9
5
4
3
2
1
233
样例输出1
283
284
284
284
284
285
285
285
286
样例输入3
样例输出3
数据规模
对于$10\%$的数据，$k = 1$。
对于$20\%$的数据，$k \leq 2$。
对于$40\%$的数据，$N, k \leq 100$。
对于$60\%$的数据，$k \leq 1000$。
对于$80\%$的数据，$N \leq 1000, k \leq 20000$。
对于$100\%$的数据，$N, k \leq 10^5$，$k \leq N!$，$0 \leq A_i \leq 10^8$。
数据有一定梯度。
题解
（稍后再补）
代码
（稍后再补）