BÀI 3. THI CÔNG

Cuối năm 2100, các công ty bắt đầu thi công bảo trì các tuyến đê biển. Gói thầu của công ty FASTBUILD là tuyến đê có N điểm thi công, mỗi điểm thi công sẽ được thanh toán số tiền tương ứng lần lượt là a₁, a₂, … , a_n.

Quy tắc thi công là phải làm theo thứ tự từ ngoài vào trong, mỗi ngày công ty sẽ thi công một điểm, có thể là điểm đầu hoặc điểm cuối của tuyến đê, sang ngày tiếp theo có thể lựa chọn lại điểm để thi công theo nguyên tắc trên. Do phải đầu tư một số tiền lớn vào nhập khẩu vật tư, trong K ngày tới, công ty cần thu hồi vốn nhiều nhất có thể. Ban giám đốc công ty đã tổ chức họp để tìm ra phương án thu hồi vốn tốt nhất.

Dữ liệu vào:

          - Dòng đầu ghi hai số nguyên dương N và K (N 10⁴, K N)

          - Dòng tiếp theo gồm N số nguyên dương a_i (a_i 10¹²)

Dữ liệu ra: Một dòng duy nhất là số tiền nhận được nhiều nhất tính đến ngày thứ K.