Giá trị lớn nhất nhỏ nhất

Cho mảng \(A\) gồm \(n\) phần tử. Hãy tìm giá trị nguyên \(x\) nhỏ nhất sao cho có thể chia mảng \(A\) thành chính xác \(k\) mảng con liên tiếp mà tổng của từng mảng con không vượt quá \(x\).

Input

• Dòng đầu tiên gồm hai số nguyên \(n, k\) (\(1 \le k \le n \le 10^5\)).

• Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(1 \le A_i \le 10^9\)).

Output

In ra một số nguyên \(x\) là đáp án.

Example

Input:

5 2
5 4 3 2 1

Output:

9

Note

Chia thành \([5, 4]\) và \([3, 2, 1]\), tổng hai đoạn là \(9\) và \(6\), lớn nhất là \(9\). Không tồn tại cách chia mảng \(A\) thành đúng \(2\) đoạn mà mọi đoạn có tổng nhỏ hơn \(9\).