Phân chia công việc

Một nhóm thợ có \(n\) công việc cần làm, mỗi công việc mất một số giờ nhất định để hoàn thành. Công việc thứ \(i\) mất \(a_i\) giờ.

Bạn được yêu cầu chia các công việc này thành \(k\) đoạn liên tiếp (các công việc trong cùng một đoạn phải liền kề nhau). Mỗi đoạn sẽ được giao cho một người thợ.

Nhiệm vụ của bạn là chia sao cho thời gian làm việc lâu nhất trong số \(k\) thợ là nhỏ nhất có thể.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq k \leq n \leq 2 \times 10^5)\).

Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) --- thời gian cần để hoàn thành công việc thứ \(i\).

Output

In ra một số nguyên --- thời gian làm việc lâu nhất mà một người thợ phải thực hiện, nếu chia công việc theo cách tối ưu.

Example

5 3
2 4 7 3 5

8

Scoring

• Subtask 1 (20 điểm): \(k = 2\)
• Subtask 2 (30 điểm): \(k = 3\)
• Subtask 3 (50 điểm): Không có ràng buộc gì thêm.