Round Table

Time limit8sMemory limit512 MB

Summary

N customers sit around a round table, M menus circulate; each customer takes Li time to order, find the minimum total time until everyone finishes ordering.

Level: Medium7 of 10
Topics: Binary search, Greedy, Array, Simulation
Solved: No attempts yet

Problem

You own a restaurant and are serving N customers seated at a round table.

You are going to distribute M menus to them. Each customer who receives a menu places an order, then passes the menu to the customer on the right unless that customer has not yet placed an order. Customer i takes Li units of time to place an order.

Write a program that computes the minimum time until all customers have placed their orders, so you can improve your business performance.

Input

The input consists of a sequence of positive integers.

The first line contains two positive integers N (N ≤ 50,000) and M (M ≤ N). The second line contains N positive integers L1, L2, ..., LN (Li ≤ 600).

Output

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

Examples2

Example 1
Input
```
3 2
1 5 10
```
Expected output
```
10
```
Example 2
Input
```
4 2
1 2 3 4
```
Expected output
```
5
```