← 返回题目列表

AtCoder · tupc2022_k

K. 勒贝格积分

中文机器翻译题面 查看原题

配点 : 400 点

問題文

长度 小于或等于 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 (A_j \in (m_{i-1}, m_i]\text{的}j\text{的个数}) \] 求其最小值。可以证明答案必定为整数。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 10^5
  • 1 \leq A_i \leq 10^5 \, (i=1,2,\dots,N)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N K
A_1 A_2 \dots A_N

出力

将答案打印为整数。


入力例 1

4 2
3 7 4 5

出力例 1

22

例如, (0,7]=(0,4]\cup(4,7] 分割为后,求得的值为 4 \times 2 + 7 \times 2 = 22 ,这是最小值。


入力例 2

19 4
3279 97197 36049 32099 29257 18290 96531 13435 88697 97081 71483 11396 77398 55303 4166 3906 12281 28658 30496

出力例 2

917886