Yêu cầu

Tổ Toán có N xấp bài kiểm tra được đặt liên tiếp trên bàn, xấp thứ i có A_i bài. Tổ trưởng cần phân công K giáo viên chấm bài. Mỗi giáo viên phải nhận một số xấp bài liên tiếp nhau. Áp lực của một giáo viên được tính bằng tổng số bài kiểm tra mà họ phải chấm.

Để đảm bảo công bằng và hoàn thành sớm tiến độ, tổ trưởng muốn cách chia sao cho giáo viên có áp lực lớn nhất phải chấm số bài là ít nhất có thể.

Yêu cầu: Đưa ra mức áp lực (tổng số bài lớn nhất của một giáo viên) nhỏ nhất có thể.

Dữ liệu vào

Đọc từ tệp PHANCONG.INP gồm:
Dòng thứ nhất chứa hai số nguyên dương N và K (N >= K).
Dòng thứ hai chứa N số nguyên dương A_1, A_2, ..., A_N.

Dữ liệu ra

Ghi ra tệp PHANCONG.OUT một số nguyên duy nhất là mức áp lực nhỏ nhất.

Ràng buộc

Subtask 1: 20% số điểm có 2 <= N <= 10; 1 <= A_i <= 100; K = 2;
Subtask 2: 30% số điểm có 10 <= N <= 100; 1 <= A_i <= 1000; 3 <= K <= 10;
Subtask 3: 50% số điểm có 100 <= N <= 10^5; 1 <= A_i <= 10^9; 3 <= K <= 10^3.

Ví dụ

Input:

5 3
2 4 1 5 3

Output:

6