AT_tupc2022_k Lebesgue Integral

给定一个长度为 $N$ 的正整数序列 $(A_1,A_2,\dots,A_N)$。令 $M = \max\,\{A_i \mid 1 \leq i \leq N\}$，将区间 $(0,M]$ 分成 $K$ 个区间。也就是说，选择非负实数 $m_i\ (i=0,1,\dots,K)$，满足 $0=m_0 < m_1 < m_2 < \dots < m_{K-1} < m_K = M$，使得 $(0,M] = (m_0,m_1] \cup (m_1,m_2] \cup \dots \cup (m_{K-1},m_K]$。 当区间划分合理时，求 \[ \displaystyle \sum_{i=1}^{K} m_i \times (\text{满足 } j \text{ 使得 } A_j \in (m_{i-1}, m_i] \text{ 的 } j \text{ 的个数}) \] 的最小值。可以证明答案必然为整数。

输入以如下格式从标准输入读入。 > $N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$

请输出一个整数，表示答案。

### 样例解释 1 例如，将 $(0,7]=(0,4]\cup(4,7]$ 分割时，所求值为 $4 \times 2 + 7 \times 2 = 22$，且这是最小值。 ### 数据范围 - $1 \leq N \leq 10^5$ - $1 \leq K \leq 10^5$ - $1 \leq A_i \leq 10^5 \quad (i=1,2,\dots,N)$ - 输入均为整数。 由 ChatGPT 5 翻译