测试数据来自 system/1142

描述

在dos系统诞生以前，大同曾研究出一种类似的操作系统，名为HXOS系统。但由于硬件设施的制约，HXOS系统有许多的缺点。下面就对HXOS系统作一个简单的介绍：
HXOS系统是HXer博士为大同军方研制开发的一种操作系统，该系统对文件的存储方式类似于dos系统，像一棵树一样，每一个叶子节点表示一个文件，每一个非叶子节点表示一个目录。其中定义 \(i\) 级子目录表示从根目录开始访问，一直访问到该子目录（不包括该子目录）需要访问的目录的个数为i的目录，所以根目录下的目录为一级子目录，其他的目录以此类推。但是在同一子目录下，受到硬件的制约HXOS系统最多只能够存储 \(k\) 个文件或子目录，也就是说这棵树里面的每一个非叶子节点最多只有 \(k\) 个子节点。这样就导致在文件数量较多的情况下，访问存储在该系统当中的文件A，往往要先访问一系列的子目录，我们称这些子目录为文件A的上级目录。例如下面这一个例子：

Root
--A1
--A2
--A3
--A4
----A4A1
----A4A2
------A4A2A1
------A4A2A2
----A4A3

当我们要访问文件A4A2A1时就必须先访问它的上级目录：一级子目录A4和二级子目录A4A2。

HXOS系统在存储文件时，给每一个子目录都分配了 \(k\) 个指针，分别指向存放在该目录下的每一个文件和每一个目录，因此对文件的访问实质上就是对指针的访问。但是由于硬件原因，这 \(k\) 个指针不尽相同，因此访问它们的时间也不同，访问第 \(i\) 个指针所耗费的时间为 \(P_i\)。但是对于两个不同的子目录（不管它们各自属于哪一级目录）而言它们各自所拥有的 \(k\) 个指针是相同的。

HXOS系统最大的缺点是访问一个目录时，必须把该目录下所有的文件读入到内存当中来，这些文件包括在其各级子目录当中的文件，例如上面那一个例子，访问A4那一个目录，就必须把A4A1，A4A2A1，A4A2A2，A4A3这四个文件都读入到内存当中来，访问一个目录所需要的时间为 \(y \times x\)（\(y = P_i\) 表示指向该目录的指针的访问时间，\(x\) 表示该目录及其各级子目录下文件的个数和）。因此根据上面介绍的访问方法，单独访问一个文件所需要的总时间为访问其所有上级目录（不包括根目录）所需要的时间与访问指向该文件的指针所需要的时间的和，例如上面那一个例子，访问文件A4A2A1需要的时间 \(=\) 访问目录A4的时间 \(+\) 访问目录A4A2的时间 \(+\) 访问指向文件A4A2A1的指针需要的时间。

现在，HXer博士准备将 \(n\) 个文件存储到一个空的HXOS系统当中，希望你帮助他设计一个程序找到一种最优的存储方法，使得单独访问这 \(n\) 个文件所需要的时间总和最小。

格式

输入格式

文件的第一行为两个正整数 \(1\le n\le 1000\) 和 \(2\le k\le 150\) ，接下来的 \(k\) 行每行有一个正整数 \(P_i\le 150\) 。

输出格式

仅有一个正整数，表示在最优存储方案下，单独访问这 \(n\) 个文件所需要的时间总和。（保证结果小于 \(2^{31}\))

样例1

样例输入1

4 3
3
5
4

样例输出1

28

限制

1 S

提示

样例的最优存储方案为：

椭圆表示目录，方形表示文件。每一图形里面的数表示访问该文件或目录所需要的时间，所以总费是 \(=(3+6)+(4+6)+5+4=28\)。

来源

huyichen