Computer Network#534
System administrator Oleksandr has a linear network of servers. The servers are connected sequentially in a chain. Each server has its own bandwidth capacity — a number from to .
Servers that are in the same network segment generate network traffic between each other. The total network load is calculated by adding up the products of bandwidth capacities for every pair of servers that are connected in the same segment. Consider this network:
[server 4] - [server 5] - [server 1] - [server 2]Its total load is: 4 \times 5 + 4 \times 1 + 4 \times 2 + 5 \times 1 + 5 \times 2 + 1 \times 2 = 49.
Oleksandr wants to reduce the total load by dividing the network into separate segments using routers (separators). Suppose he can install only one router. If he divides the network in the middle:
[server 4] - [server 5] | [server 1] - [server 2]Total load: 4 \times 5 + 1 \times 2 = 22. But if Oleksandr divides between servers and :
[server 4] | [server 5] - [server 1] - [server 2]Total load: 5 \times 1 + 5 \times 2 + 1 \times 2 = 17. This is the best option.
Given a description of a network and the number of routers that Oleksandr can install, determine the smallest total network load he can achieve.
There will be several data sets. Each data set will begin with a line with two integers, and . is the number of servers in the network (1 \le n \le 1000), and is the number of routers Oleksandr can install (0 \le m < n). On the next line will be integers, each from to , indicating the bandwidth capacity of each server in order. The end of input will be marked by a line with n = 0 and m = 0, which should not be processed.
For each data set, output a single integer, indicating the smallest total network load that Oleksandr can achieve with his routers. Output each integer on its own line.
Example 1