[HNOI2002]Tinux系统

在 DOS 系统诞生以前，美国曾研究出一种类似的操作系统，名为 Tinux 系统。该系统由 Tiger 博士为美国军方研制，其文件存储结构与 DOS 系统类似，可以表示为一棵树：每个叶子节点表示一个文件，每个非叶子节点表示一个目录。

从根目录开始访问某个目录时，在到达该目录之前需要经过 $i$ 个目录，则称该目录为 $i$ 级子目录。因此，根目录下的目录称为一级子目录，其余目录依此类推。

受硬件限制，每个目录下最多只能存储 $K$ 个文件或子目录，即树中的每个非叶子节点最多有 $K$ 个子节点。访问一个文件时，通常需要先依次访问它的所有上级目录。例如，要访问文件 $\mathrm{A4A2A1}$ ，必须先访问其一级上级目录 $\mathrm{A4}$ 和二级上级目录 $\mathrm{A4A2}$ 。

Tinux 系统为每个目录分配了 $K$ 个指针，分别指向该目录下的文件或子目录，因此对文件和目录的访问实质上是对指针的访问。由于硬件原因，这 $K$ 个指针的访问时间不同，访问第 $i$ 个指针所需的时间为 $P_i$ 。所有目录均使用相同的 $K$ 种指针。

Tinux 系统在访问一个目录时，必须将该目录及其各级子目录下的所有文件读入内存。若指向某个目录的是第 $i$ 个指针，并且该目录及其各级子目录下共有 $x$ 个文件，则访问该目录所需的时间为 $xP_i$ 。

单独访问一个文件所需的总时间，等于访问其所有上级目录（不包括根目录）所需的时间，加上访问指向该文件的指针所需的时间。例如，访问文件 $\mathrm{A4A2A1}$ 所需的时间为：访问目录 $\mathrm{A4}$ 的时间、访问目录 $\mathrm{A4A2}$ 的时间，以及访问指向文件 $\mathrm{A4A2A1}$ 的指针所需时间之和。

现在，Tiger 博士准备将 $N$ 个文件存储到一个空的 Tinux 系统中。请设计一种最优的存储方案，使得分别单独访问这 $N$ 个文件所需时间的总和最小。

输入格式

第一行包含两个正整数 $N,K$ 。

接下来 $K$ 行，第 $i$ 行包含一个正整数 $P_i$ ，表示每个目录中第 $i$ 个指针的访问时间。

输出格式

输出一个整数，表示在最优存储方案下，分别访问这 $N$ 个文件所需时间的总和。

样例输入

样例输出

数据范围

$1\le N\le 1000$ ；
$2\le K\le 150$ ；
$1\le P_i\le 150$ ；
保证答案小于 $2^{31}$ 。

来源与许可

本题为 HNOI 2002 试题「Tinux 系统」，题面与测试数据整理自 BZOJ。

样例 1

输入