DMOPC '21 Contest 8 P5 - Tree Building

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

For her final CS project, Mafuyu needs to build a tree with N nodes. Where is she going to get the nodes from? The convenience store, of course! The convenience store offers a wide variety of nodes for various prices. Specifically, for each 1 \le i \le K, it has an unlimited supply of nodes with i connectors coming out of it for a_i yen each.

After buying the required nodes, Mafuyu needs to go home and actually build the tree by repeatedly melding two connectors from two different nodes into a single edge connecting the two nodes. The final product should not have any leftover connectors that are not melded.

Given these conditions, please find the minimum total cost required for Mafuyu to build a tree with N nodes!


3 \le N \le 10^9

2 \le K \le 3 \times 10^3

K < N

1 \le a_i \le 10^9

Subtask 1 [15%]

N \le 300

Subtask 2 [20%]

N \le 3 \times 10^3

Subtask 3 [20%]

N \le 2 \times 10^5

K \le 300

Subtask 4 [20%]

K \le 300

Subtask 5 [25%]

No additional constraints.

Input Specification

The first line contains 2 space-separated integers N and K.

The next line contains K space-separated integers a_1, a_2, \dots, a_K.

Output Specification

Output the minimum total cost (in yen) required for Mafuyu to build a tree with N nodes.

Sample Input

4 3
1 3 4

Sample Output



Mafuyu can buy 3 nodes with 1 connector and 1 node with 3 connectors, forming the following tree:


There are no comments at the moment.