## DMOPC '21 Contest 8 P5 - Tree Building

View as PDF

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

Author:
Problem type

For her final CS project, Mafuyu needs to build a tree with 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 , it has an unlimited supply of nodes with connectors coming out of it for 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 nodes!

#### Input Specification

The first line contains space-separated integers and .

The next line contains space-separated integers .

#### Output Specification

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

#### Sample Input

4 3
1 3 4

#### Sample Output

7

#### Explanation

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