P2230 [HNOI2002] Tinux System

# Description Before the DOS system was born, the United States studied a similar operating system called the Tinux system. However, due to hardware limitations, the Tinux system had many drawbacks. Below is a brief introduction to the Tinux system. The Tinux system was developed by Dr. Tiger for the U.S. military. Its file storage method is similar to DOS: it is like a tree, where each leaf node represents a file, and each non-leaf node represents a directory. We define an $i$-level subdirectory as a directory such that, starting from the root directory, the number of directories that must be visited to reach (but not including) this subdirectory is $i$. Therefore, directories directly under the root are level 1 subdirectories, and so on. Within any single directory, due to hardware limits, the Tinux system can store at most $k$ files or subdirectories. In other words, every non-leaf node in this tree has at most $k$ children. As a result, when there are many files, to access a file A stored in the system, one often has to visit a sequence of directories first; we call these directories the ancestor directories of file A. For example:  When we want to access file A4A2A1, we must first visit its ancestor directories: the level-1 directory A4 and the level-2 directory A4A2. When storing files, the Tinux system allocates $k$ pointers to every directory, each pointing to one file or subdirectory under it. Therefore, accessing a file is essentially accessing pointers. However, due to hardware reasons, these $k$ pointers are not identical, so the time to access them is different: the time to access the $i$-th pointer is $P_i$. For two different directories (regardless of their depth), their sets of $k$ pointers are the same. The biggest drawback of the Tinux system is that when accessing a directory, all files under that directory must be read into memory, including files in all its subdirectories. For example, in the figure above, accessing directory A4 requires loading four files into memory: A4A1, A4A2A1, A4A2A2, and A4A3. The time to access a directory is $P_i \times x$ (where $x$ is the number of files under that directory and all of its subdirectories, and $P_i$ is the time to access the pointer pointing to that directory). Therefore, according to the access method described above, the total time to access a single file equals the sum of the times to access all its ancestor directories (excluding the root) plus the time to access the pointer to that file. For example, in the figure above, the time to access file A4A2A1 = the time to access directory A4 + the time to access directory A4A2 + the time to access the pointer to file A4A2A1. Now, Dr. Tiger plans to store $n$ files into an empty Tinux system. Please help him design a program to find an optimal storage plan that minimizes the total time needed to access these $n$ files individually.

在 dos 系统诞生以前，美国曾研究出一种类似的操作系统，名为 Tinux 系统。但由于硬件设施的制约，Tinux 系统有许多的缺点。下面就对 Tinux 系统作一个简单的介绍： Tinux 系统是 Tiger 博士为美国军方研制开发的一种操作系统，该系统对文件的存储方式类似于 dos 系统，像一棵树一样，每一个叶子节点表示一个文件，每一个非叶子节点表示一个目录。其中定义 $i$ 级子目录表示从根目录开始访问，一直访问到该子目录（不包括该子目录）需要访问的目录的个数为 $i$ 的目录，所以根目录下的目录为一级子目录，其他的目录以此类推。但是在同一子目录下，受到硬件的制约 Tinux 系统最多只能够存储 $k$ 个文件或子目录，也就是说这棵树里面的每一个非叶子节点最多只有 $k$ 个子节点。这样就导致在文件数量较多的情况下，访问存储在该系统当中的文件 A，往往要先访问一系列的子目录，我们称这些子目录为文件 A 的上级目录。例如下面这一个例子：  当我们要访问文件 A4A2A1 时就必须先访问它的上级目录：一级子目录 A4 和二级子目录 A4A2。 Tinux 系统在存储文件时，给每一个子目录都分配了 $k$ 个指针，分别指向存放在该目录下的每一个文件和每一个目录，因此对文件的访问实质上就是对指针的访问。但是由于硬件原因，这 $k$ 个指针不尽相同，因此访问它们的时间也不同，访问第 $i$ 个指针所耗费的时间为 $P_i$。但是对于两个不同的子目录（不管它们各自属于哪一级目录）而言它们各自所拥有的 $k$ 个指针是相同的。 Tinux 系统最大的缺点是访问一个目录时，必须把该目录下所有的文件读入到内存当中来，这些文件包括在其各级子目录当中的文件，例如上面那一个例子，访问 A4 那一个目录，就必须把 A4A1，A4A2A1，A4A2A2，A4A3 这四个文件都读入到内存当中来，访问一个目录所需要的时间为 $P_i \times x$（$x$ 表示该目录及其各级子目录下文件的个数，$P_i$ 表示指向该目录的指针的访问时间）。因此根据上面介绍的访问方法，单独访问一个文件所需要的总时间为访问其所有上级目录（不包括根目录）所需要的时间与访问指向该文件的指针所需要的时间的和，例如上面那一个例子，访问文件 A4A2A1 需要的时间 = 访问目录 A4 的时间 + 访问目录 A4A2 的时间 + 访问指向文件 A4A2A1 的指针需要的时间。 现在，tiger 博士准备将 $n$ 个文件存储到一个空的 Tinux 系统当中，希望你帮助他设计一个程序找到一种最优的存储方法，使得单独访问这 $n$ 个文件所需要的时间总和最小。

文件的第一行为两个正整数 $n, k$，接下来的 $k$ 行每行有一个正整数 $P_i$。

Output a single positive integer: under the optimal storage plan, the total time required to access these $n$ files individually (the result is less than $2^{31}$).

 Constraints $1 \le n \le 1000$, $2 \le k \le 150$, $1 \le P_i \le 150$. Translated by ChatGPT 5