The Farmer get a string of consecutive pearls, it contants N pearls. each pearls worth W_i. Unfortunately, the Landlord discover these pearls, the Landlord require the Farmer divide the string of pearls into M short consecutive pearls, and the Landlord will get The most expensive short consecutive pearls.

The Farmer want to give the Landlord short consecutive pearls as cheap as possible.

This problem has several cases.
for each case, first line have two integer N(1 <= N <= 10^6) and M (1 <= M <= N)
the second line have N integer, it means the Wi(i = 1 ... N, 1 <= Wi <= 100).

For each case, print the least wealth of the short consecutive pearls Landlord will get.