DoMixi và HakyFood qua nhà ông chơi. Ông chia cho hai đứa rất nhiều kẹo.

HakyFood được ông giao nhiệm vụ chia kẹo. Ban đầu có ~n~ gói kẹo, mỗi gói chứa lượng kẹo nào đó. HakyFood đang có ~k~ cái hộp, mỗi hộp có thể cho lượng kẹo bất kỳ vào đó nhưng chỉ được chứa kẹo của một gói duy nhất. Hộp cũng có thể không chứa kẹo.

HakyFood phải chia DoMixi ~k/2~ hộp kẹo có nhiều kẹo nhất mà cậu đã chia. DoMixi có thể được chia nhiều kẹo hơn.

HakyFood rất thích kẹo nên muốn chia để sao cho lượng kẹo của cậu là lớn nhất có thể mà vẫn đảm bảo chia đúng quy tắc. Các bạn hãy giúp HakyFood nhé!

Input

Dòng đầu chứa hai số nguyên ~n, k~ (~1 \le n, k \le 10^3~, k chẵn)   – Số lượng gói kẹo và số lượng cái hộp.

Dòng tiếp theo chứa ~n~ số nguyên ~c_i~ (~1 \le c_i \le 10^3~)  – Mô tả số kẹo ở gói kẹo thứ ~i~.

Output

In ra số nguyên duy nhất là đáp án của bài.

Example

Input

4 4
5 9 6 4

Output

9

Note

Ở test ví dụ, HakyFood sẽ chia gói thứ ~2~ vào ~2~ hộp chứa ~5~ và ~4~, gói thứ ~3~ vào ~1~ hộp chứa ~5~ và gói ~1~ vào ~1~ hộp chứa ~5~. DoMixi sẽ được ~10~ cái kẹo còn HakyFood sẽ được ~9~ cái kẹo.