Cho một mảng chứa ~N~ số nguyên dương ~x_1, x_2, ..., x_N~. Hãy chia mảng thành ~K~ đoạn con liên tiếp sao cho tổng lớn nhất trong các đoạn con đó là nhỏ nhất có thể.

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên ~N~ và ~K~.
• Dòng tiếp theo chứa ~N~ số nguyên dương ~x_1, x_2, ..., x_N~ là giá trị các phần tử của mảng.

Output

• In một số nguyên là tổng lớn nhất của một đoạn con trong cách chia tối ưu.

Giới hạn:

• ~1 \leq K \leq N \leq 2*10^5~
• ~1 \leq X_i \leq 2*10^9~

Sample input

5 3
2 4 7 3 5

Sample Output

8

Giải thích:

• Một cách chia tối ưu là ~(2,4), (7), (3,5)~. Trong đó tổng của các đoạn con là ~6, 7, 8~. Tổng lớn nhất trong cách chia nàu là ~8~.