Cho \(n\) món hàng được đưa ra theo thứ tự và \(k\) xe tải. Mỗi món hàng khi đưa ra đều được đưa lên xe tải, mỗi xe tải có một tải trọng \(w\) là khối lượng có thể chịu được. Cho khối lượng \(a[i]\) của các món hàng được đưa ra theo thứ tự, tính \(w\) bé nhất có thể sao cho sử dụng không quá \(k\) xe tải.

Input

• Dòng đầu tiên là \(2\) số \(n\) và \(k\) \((1 \le k \le n \le 2 \times 10^5)\).
• Dòng thứ hai là \(n\) số \(a[i] (1 \le a[i] \le 10^9)\).

Output

• Chính xác \(1\) số là số \(w\) cần tìm.

5 2
3 2 4 5 1

9