Cho một dãy sỏi gồm \(n\) đống \(a_1,a_2,…,a_n \) mỗi đống sỏi có ít nhất 1 viên sỏi.

Yêu cầu: Hãy chia dãy sỏi này thành \(k\) đoạn liên tục sao cho tổng số sỏi lớn nhất trong các đoạn này là nhỏ nhất. Biết số viên sỏi trong mỗi đoạn không vượt quá 10^9.

Input

• Dòng thứ nhất chứa 2 số nguyên dương \(n\) và \(k (1≤k≤n≤10^5);\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1≤a_i≤10^9).\)

Output

• Ghi ra tổng số sỏi lớn nhất trong các đoạn sau khi chia sao cho giá trị đó là giá trị nhỏ nhất có thể.

Ràng buộc

• Giải thích: Có thể chia thành các đoạn: (1 3 2 4) (10) (8 4) (2 5 3)

Sample Input

10 4
1 3 2 4 10 8 4 2 5 3

Sample Output

12