Có N công việc được xếp thành một hàng ngang theo thứ tự từ 1 đến N. Người ta sử dụng 2 máy là máy A và máy B để xử lý công việc tự động. Cả hai máy chỉ được phép xử lý các công việc tuần tự, xử lý xong việc này rồi mới được sang việc kế tiếp (thời gian chuyển tiếp giữa 2 việc là không đáng kể). Máy A được đặt ở đầu bên trái, chỉ xử lý các công việc từ trái sang phải: 1, 2, 3... (nếu được phân công). Tương tự, máy B được đặt ở đầu bên phải, chỉ được thực hiện tuần tự các công việc từ phải sang trái: N, N-1,... (nếu được phân công). Công việc thứ i sẽ mất Ai đơn vị thời gian để xử lý xong, bất kể là do máy nào thực hiện.

Yêu cầu: Chọn ra K công việc và phân công cho 2 máy xử lý sao cho thời gian xử lý xong toàn bộ K công việc đó là ít nhất. Biết rằng, cả hai máy đều bắt đầu làm việc ở thời điểm 0, làm việc song song và mỗi công việc được chọn phải được một và chỉ một máy xử lý đúng một lần.

Dữ liệu:

• Dòng đầu chứa hai số nguyên dương N và K (K ≤ N ≤ 10^5).
• Dòng thứ hai chứa N số nguyên dương A1, A2,...,AN; (Ai ≤ 10^9 với mọi i = 1..N).

Kết quả: Đưa ra một số nguyên duy nhất là thời gian ít nhất để xử lý xong K công việc như yêu cầu.

Ví dụ:

HAIMAY.INP

5 4
4 3 1 2 3

HAIMAY.OUT

6

Giải thích: Máy A thực hiện công việc 1, còn máy B thực hiện các công việc 3,4,5.

Ràng buộc:

● Có 25% số test, tương ứng với 25% số điểm có N ≤ 10^4

● Có 75% số test, tương ứng với 75% số điểm còn lại không còn ràng buộc gì thêm.

Nguồn