Background

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.

Output Format

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}$).

4 3
3
5
4

28

Hint

Constraints

$1 \le n \le 1000$, $2 \le k \le 150$, $1 \le P_i \le 150$.

Translated by ChatGPT 5