Mô tả bài toán

Cho một mảng gồm ~ n ~ số nguyên dương. Yêu cầu chia mảng thành ~ k ~ đoạn (mảng con liên tiếp) sao cho:

• Tổng lớn nhất trong các đoạn là nhỏ nhất có thể.

Nhiệm vụ của bạn là tìm giá trị nhỏ nhất của tổng lớn nhất đó.

Input

• Dòng đầu tiên: Hai số nguyên ~ n ~ và ~ k ~ (1 ≤ ~ k \leq n \leq 2 \times 10^5 ~).
• Dòng thứ hai: ~ n ~ số nguyên ~ x_1, x_2, ..., x_n ~ (1 ≤ ~ x_i \leq 10^9 ~).

Output

• Một số nguyên: Giá trị nhỏ nhất của tổng lớn nhất trong các đoạn.

Ví dụ minh họa

Input

5 3
2 4 7 3 5

Output

8

Giải thích:

• Chia mảng:
  • Đoạn 1: ~ [2, 4] ~, tổng = 6.
  • Đoạn 2: ~ [7] ~, tổng = 7.
  • Đoạn 3: ~ [3, 5] ~, tổng = 8.
• Số đoạn: 3 (hợp lệ).