Optimal File Storage in Tinux System

Tinux is an operating system developed by Dr. Tiger for the US military before DOS was invented. In Tinux, files are stored in a tree‐like directory structure. Each non‐leaf (directory) node can have at most k children (each child may be either a file or a subdirectory), and each child is accessed via one of k pointers. The pointers have different access times. In every directory the k pointers have associated access times \(P_1, P_2, \ldots, P_k\) (given in latex as \(P_i\) for the ith pointer). When a directory is accessed through its parent’s pointer, all files in the directory and in any subdirectories under it are read into memory. Hence, if a directory is accessed via pointer \(i\) and its subtree contains \(x\) files, the access time is \(P_i\times x\). In addition, to access a file, the pointers used to enter each directory along the path (except the root) are all traversed, and finally the pointer to the file in its parent directory is used (this final pointer access is not multiplied by any file count).

More formally, consider a storage layout for n files. Each file is stored as a leaf in a tree (other nodes are directories). For every non‐root node (be it a file or a directory) that is attached to its parent using the ith pointer in that directory, if the subtree rooted at that node contains \(f\) files then this pointer access contributes a cost of \(P_i \times f\) (when the node is a file, \(f=1\); when it is a directory, it is the total number of files in its subtree). The total access time for a file is the sum of the costs on all pointers along the path from the root (excluding the root) to that file. The goal is to arrange the storage of the n files (possibly by adding directories arbitrarily, keeping the constraint of at most k children per directory) so that the sum of the individual access times for the n files is minimized.

You are given an empty Tinux system. Dr. Tiger will store n files into the system. Your task is to compute the minimum total access time needed to access all files (assuming each file is accessed individually) if the system is optimally organized. Note that within every directory, you may arrange the children arbitrarily. In an optimal arrangement, the children of a directory will be sorted by their file‐counts in descending order and assigned the pointers with increasing access times accordingly. Also, if a directory has \(m\) children (with \(m\le k\)) and if all children are files then the cost to store them is \(\sum_{i=1}^{m} P_i\).

Input Format: See below.

inputFormat

The input consists of two lines.

The first line contains two positive integers n and k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁵), representing the number of files to store and the maximum number of pointers per directory.

The second line contains k positive integers: \(P_1, P_2, \ldots, P_k\) (each at most 10⁹), representing the access time for the corresponding pointer. (Note: The pointers in any directory can be reassigned arbitrarily – effectively you can use the sorted order of these costs in increasing order.)

outputFormat

Output a single integer, representing the minimum total access time required to access all the n files.

sample

2 2
3 5

8