Bessie và em gái nhỏ của cô, Elsie, đang hái quả trong vườn quả của Farmer John. Vườn của Farmer John có \(N\) cây, cây thứ \(i\) có \(a_i\) quả.

Bessie có \(K\) giỏ. Mỗi giỏ có thể chứa không giới hạn số quả nhưng quả bỏ vào một giỏi phải từ một cây mà Bessie muốn, không thể chứa quả từ hai cây khác nhau vì hương vị sẽ bị lẫn lộn. Các giỏ có thể để trống.

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

Yêu cầu: Hãy giúp Bessie tìm cách hái quả từ các cây bỏ vào \(K\) giỏ sao cho số lượng quả mà cô có thể nhận được là nhiều nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 ≤ N, K ≤ 1000, K\) chẵn).

• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,…,a_N (1 ≤ a_i ≤ 1000)\).

Output

• Số lượng quả lớn nhất mà Bessie nhận được

Sample Input

5 4
3 6 8 4 2

Sample Output

8

Ràng buộc:

• Subtask 1: 40% test với K≤10

• Subtask 2: 60% test không có ràng buộc gì thêm.

Giải thích:

• Cây 2: Có 6 quả. Bessie có thể cho vào 1 giỏ chứa 6 quả.

• Cây 3: Có 8 quả. Bessie có thể cho vào 2 giỏ, mỗi giỏ chứa 4 quả (vì 8 quả chia cho 2 giỏ sẽ được 4 quả mỗi giỏ).

• Cây 4: Có 4 quả. Bessie có thể cho vào 1 giỏ chứa 4 quả.

Vậy số lượng quả trong 4 hioir lần lượt là : 6 4 4 4:

• Elsie sẽ nhận 2 giỏ có số lượng quả nhiều nhất = 6 + 4 = 10.

• Bessie nhận 2 giỏ còn lại với số lượng quả = 4 + 4 = 8

Tổng số quả mà Bessie nhận được là 8 quả (2 giỏ với 4 quả).