You are the owner of a restaurant, and you are serving for *N* customers seating in a round table.

You will distribute *M* menus to them. Each customer receiving a menu will make the order of plates, and
then pass the menu to the customer on the right unless he or she has not make the order. The customer *i* takes *L _{i}* unit time for the ordering.

Your job is to write a program to calculate the minimum time until all customers to call their orders, so you can improve your business performance.

The input consists of a sequence of positive integers.

The first line of the input contains two positive integers *N* (*N* ≤ 50,000) and *M* (*M* ≤ *N*). The second line contains *N* positive integers *L*_{1}, *L*_{2},..., *L _{N}* (

Output the minimum possible time required for them to finish ordering.

3 2 1 5 10

10

4 2 1 2 3 4

5

Source: ACM-ICPC Japan Alumni Group Winter Camp
, Day 3, Tokyo, Japan, 2009-02-23

http://acm-icpc.aitea.net/

http://acm-icpc.aitea.net/