Bessie và em gái Elsie đang hái quả mọng trong vườn cây của Farmer John. Khu vườn có đúng \(N\) cây quả mọng (\(1\le N\le 1000\)); cây thứ \(i\) có đúng \(B_i\) quả (\(1\le B_i\le 1000\)). Bessie có đúng \(K\) chiếc giỏ (\(1\le K\le 1000\), \(K\) là số chẵn). Mỗi giỏ có thể chứa bao nhiêu quả từ một cây tùy ý Bessie muốn, nhưng không thể chứa quả từ hai cây khác nhau vì hương vị của chúng sẽ xung khắc. Các giỏ có thể được để trống.

Bessie muốn tối đa hóa số quả mình thu hoạch được. Tuy nhiên, Farmer John muốn Bessie chia sẻ với em gái, vì vậy Bessie sẽ phải đưa cho Elsie \(K/2\) chiếc giỏ có số quả nhiều nhất. Điều này có nghĩa là Elsie thậm chí có thể nhận được nhiều quả hơn Bessie, thật vô cùng bất công, nhưng tiếc thay, quan hệ giữa chị em không phải lúc nào cũng công bằng.

Hãy giúp Bessie xác định số quả tối đa mà cô có thể thu được.

Phân nhóm

• Các test từ \(1\) đến \(4\) thỏa mãn \(K\le 10\).
• Các test từ \(5\) đến \(11\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp berries.in.

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 \(B_1,B_2,\ldots,B_N\), cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra tệp berries.out một dòng chứa đáp án.

Ví dụ

5 4
3 6 8 4 2

8

Nguồn

• Kỳ thi: USACO 2020 January Contest, Silver
• Tên bài: Berry Picking
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=990
• Tác giả đề: Nathan Pinsker