(chonqua_hd.*)

Lớp 12A1 có \(n\) bạn nam và \(m\) bạn nữ, số lượng bạn nam không ít hơn số lượng bạn nữ. Nhân ngày Phụ nữ Việt Nam (20/10), các bạn nam quyết định mua quà tặng cho các bạn nữ. Mỗi bạn tự mình sẽ mua một gói quà. Do không bàn bạc nên giá trị của các gói quà tặng cũng khác nhau. Lớp trưởng Dũng bày các gói quà thành một hàng với trị giá các gói quà là \(a_{1},\ a_{2},\ \ldots\ ,\ a_{n}\) lần lượt từ trái qua phải. Sau khi phát biểu lời chúc mừng, Dũng mời lần lượt các bạn nữ trong lớp lên nhận quà với yêu cầu mỗi bạn nữ khi lên nhận quà được chọn một gói quà là một trong hai gói quà ngoài cùng (bên trái nhất hoặc bên phải nhất) trong dãy các gói quà còn lại. Mai Phương (Bí thư chi đoàn - một bạn nữ trong lớp) quyết định thảo luận với tất cả các bạn nữ để tìm ra phương án chọn quà sao cho tổng giá trị của \(m\) món quà mà các bạn nữ nhận được là lớn nhất.

Yêu cầu: Hãy viết một chương trình nhỏ giúp Mai Phương cùng các bạn nữ tính toán xem tổng giá trị lớn nhất của các gói quà mà 𝑚 bạn nữ nhận được là bao nhiêu?

Dữ liệu vào:

+ Dòng thứ nhất chứa hai số nguyên dương \(n,\ m\ (1\ \leq \ m\ \leq \ n\ \leq \ 10^{6})\) cách nhau bằng dấu trống (space).

+ Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1},\ a_{2},\ \ldots\ ,\ a_{n}\ (1\ \leq \ a_{i}\ \leq \ 10^{9}\ \forall i)\) cách nhau bằng dấu trống (space) là giá trị của 𝑛 món quà tính từ trái sang phải.

Kết quả: Ghi ra màn hình một số nguyên là tổng giá trị lớn nhất của các gói quà mà 𝑚 bạn nữ lựa chọn.

Ví dụ:

Ràng buộc:

+ 5 tests có \(n\ \leq \ 5000\ \)

+ 3 tests còn lại \(5000\ < \ n\ \leq \ 10^{6}\ \)