Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Osman Ay.
Trunk
The wood company Moon-Wood is dealing with the business
of cutting down the old trees in the Alpine forest and
selling them. The company used to carry the trunks to the
factory via rivers and cut them into smaller pieces in
the factory. However, the company has some difficulty
in carrying the big trunks to the factory due to the
decrease in the water level. In order to solve this
problem the company decided to cut trunks into pieces,
in the forest, and float the pieces to the factory.
Cutting a trunk into two pieces has a cost, which
is equal to the length of the trunk. Make a program
to calculate the minimum cost of cutting a trunk
with the length L into the N smaller pieces with
the lengths of L1, L2… Ln. At a time, you can cut
a trunk only into two pieces.
Input specification
The input consists of two lines. In the first line,
there are two integers: L and N, where L denotes the
length of the trunk and N denotes the number of
the pieces and 1 ≤ L ≤ 100.000; 1 ≤ N ≤
40.000. In the second line, there
are N positive integers separated with a space
representing the lengths of the pieces. The sum
of the numbers in the second line is always equal
to L.
Output specification
Output contains an integer that is the minimum cost of
cutting the given trunk into the given smaller pieces.
Sample Input I
10 5
1 3 2 1 3
|
Sample Input II
20 6
2 4 4 8 1 1
|
Sample Output I
22
|
Sample Output II
46
|
Для отправки решений необходимо выполнить вход.
|