Ngăn xếp và Hàng đợi

Trong một buổi đàm phán kinh doanh quốc tế, FullHouse Dev đã nhận được một thử thách thú vị từ đối tác Nissan. Họ cần phải tối ưu hóa quy trình xử lý các đơn hàng bằng cách sử dụng cả ngăn xếp và hàng đợi.

Bài toán

FullHouse Dev được cung cấp một ngăn xếp gồm \(N\) số nguyên, trong đó phần tử đầu tiên đại diện cho đỉnh của ngăn xếp và phần tử cuối cùng đại diện cho đáy của ngăn xếp. Họ cần lấy ra ít nhất một phần tử từ ngăn xếp. Tại một thời điểm bất kỳ, họ có thể chuyển đổi ngăn xếp thành hàng đợi, trong đó đáy của ngăn xếp sẽ trở thành đầu của hàng đợi. Sau khi chuyển đổi, không thể chuyển hàng đợi trở lại thành ngăn xếp. Nhiệm vụ là loại bỏ đúng \(K\) phần tử sao cho tổng của \(K\) phần tử được loại bỏ là lớn nhất.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) cách nhau bởi dấu cách.
• Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách biểu diễn các phần tử của ngăn xếp.

OUTPUT FORMAT:

• In ra tổng lớn nhất có thể của \(K\) phần tử đã loại bỏ.

Ràng buộc:

• Giới hạn thời gian: 1 giây
• Giới hạn bộ nhớ: 256MB

Ví dụ

INPUT

10 5
10 9 1 2 3 4 5 6 7 8

OUTPUT

40

Giải thích

• Lấy ra hai phần tử từ ngăn xếp: {10, 9}
• Sau đó chuyển ngăn xếp thành hàng đợi và lấy ra ba phần tử đầu tiên từ hàng đợi: {8, 7, 6}
• Tổng lớn nhất có thể là: 10 + 9 + 8 + 7 + 6 = 40