Độ rộng cửa sổ

Trong một vụ án đặc biệt, FullHouse Dev đang hỗ trợ cảnh sát điều tra một manh mối được giấu trong một chương trình máy tính cũ. Họ phát hiện ra một thử thách liên quan đến việc hiển thị văn bản trong một cửa sổ có độ rộng tối thiểu. Với kinh nghiệm lập trình của mình, FullHouse Dev bắt đầu phân tích vấn đề này.

Bài toán

FullHouse Dev có một chuỗi gồm \(n\) từ, trong đó độ dài của từ thứ \(i\) là \(L_i\). Các từ được hiển thị trong cửa sổ và được ngăn cách bởi khoảng trắng. Khi hiển thị trong cửa sổ có độ rộng \(w\), các điều kiện sau phải được thỏa mãn:

• Từ đầu tiên được hiển thị ở đầu dòng đầu tiên
• Từ thứ \(i\) (với \(i > 1\)) được hiển thị sau từ thứ \(i-1\) với khoảng cách 1 đơn vị, hoặc ở đầu dòng tiếp theo
• Độ rộng của mỗi dòng không được vượt quá \(w\)
• Một từ không được tách thành nhiều dòng

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) - số lượng từ và số dòng yêu cầu
• Dòng thứ hai chứa \(n\) số nguyên \(L_1, L_2, ..., L_n\) - độ dài của từng từ

OUTPUT FORMAT:

• In ra độ rộng tối thiểu \(w\) của cửa sổ để có thể hiển thị tất cả các từ trong \(k\) dòng hoặc ít hơn

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq k \leq n\)
• \(1 \leq L_i \leq 10^9\)

Ví dụ

INPUT

6 4
5 4 3 6 2 4

OUTPUT

8

Giải thích

Có thể chứng minh rằng không thể xếp các từ này vào 4 dòng hoặc ít hơn với độ rộng cửa sổ nhỏ hơn hoặc bằng 7. Độ rộng tối thiểu cần thiết là 8.