Description

Cupa 正在使用 $n$ 台计算机和一个集线器搭建一个连通的网络。

这些计算机编号为 $1$ 到 $n$。每台计算机 $i$ 有一根输出线缆，可以在 $d_i$ 毫秒内将 1 位数据传输到另一端。

集线器有 $k$ 个端口，可以连接计算机的线缆，每台计算机只有一个端口。

Cupa 要求每台计算机的线缆必须连接到某个端口——可以是集线器的端口，也可以是另一台计算机的端口。同时，必须保证每台计算机都能将数据传输到集线器，无论是直接连接还是通过其他计算机中转。

每台计算机 $i$ 的网络延迟 $t_i$ 定义为从计算机 $i$ 向集线器发送 1 位数据所需的时间。假设中转的计算机将收到的数据立即通过自己的输出线缆转发，不需要额外时间。

网络搭建完成后，Cupa 会计算每台计算机的网络延迟 $t_i$。他希望所有计算机的总网络延迟 $t_1 + t_2 + \ldots + t_n$ 尽可能小。

请帮助 Cupa 设计网络连接方案，使总网络延迟最小。

Input Format

第一行包含两个整数 $n$ 和 $k$，分别表示计算机数量和集线器的端口数量（$1 \leq k \leq n \leq 100$）。

第二行包含 $n$ 个整数 $d_1, d_2, \ldots, d_n$，表示每台计算机线缆的数据传输时间（$1 \leq d_i \leq 100$）。

Output Format

输出一个整数，表示最小可能的总网络延迟。

3 2
20 30 10

70

5 1
10 10 10 10 10

150

5 2
10 10 10 10 10

90

6 3
5 6 2 3 1 4

27

Hint

在第一个样例中，Cupa 应该将第 2 台和第 3 台计算机连接到集线器，将第 1 台计算机连接到第 3 台计算机。此时 $t_1 = 20 + 10 = 30$，$t_2 = 30$，$t_3 = 10$。答案为 $t_1 + t_2 + t_3 = 70$。

在第二个样例中，所有计算机应按任意顺序串联成一条链，最终连接到集线器。总网络延迟为 $10 + 20 + 30 + 40 + 50 = 150$。

由 ChatGPT 4.1 翻译