Gần thành Baghdad có một mỏ vàng, khi xưa nổi tiếng với trữ lượng rất lớn, nay bị bỏ hoang sau khi bị động đất và bão cát vùi lấp. Trong một lần lang thang dạo chơi, Aladdin và thần đèn tình cờ phát hiện ra một lối vào hang bí mật, không bị cát vùi. Sau nhiều ngày thám thính, Aladdin đã tìm được đường đến khu quặng chính. Ở đây Aladdin tìm thấy ~N~ xe goòng (loại xe chạy trên đường ray, dùng để chuyên chở đất đá, vật liệu trong các mỏ quặng) chứa đầy vàng, do trong lúc hoảng loạn do sập hang các thợ mỏ đều bỏ của chạy lấy người.

Dĩ nhiên Aladdin muốn đem hết tất cả vàng trong quặng ra nhưng sức lực có hạn, thế nên lại phải nhờ đến tài phép của thần đèn! Sau bao lần giúp đỡ "không công", lần này thần đèn quyết đòi Aladdin phải "chia chác". Sau hồi lâu thương lượng, thần đèn và Aladdin đạt được thỏa thuận: thần đèn sẽ hóa phép đưa ~K~ xe goòng ra khỏi hang, đổi lại thần đèn sẽ được tùy ý chọn số vàng cho mình. Tuy nhiên số vàng mà thần đèn nhận được phải là ước của số vàng trên mỗi xe trong số ~K~ xe này. May mắn thay, lượng vàng trên mỗi xe (tính bằng kg) trong cả ~N~ xe đều là số nguyên dương. Cho ~N~, ~K~ và dãy ~A_{i}~ thể hiện số kg vàng trên mỗi xe. Hãy tính xem số vàng lớn nhất mà thần đèn nhận được là bao nhiêu.

Input

Dòng thứ nhất gồm ~2~ số nguyên dương ~N~ và ~K~.

~N~ dòng sau, dòng thứ ~i~ gồm một số nguyên dương ~A_{i}~ là lượng vàng (theo kg) trên xe thứ ~i~.

Output

Một số nguyên dương duy nhất là số kg vàng lớn nhất mà thần đèn có thể nhận được

Giới hạn

• ~N \le 3000~;
• ~K \le 100~, ~K \le N~
• ~1 \le A_{i} \le 10^{10}~
• Subtask ~1~ (~33~%): ~N \le 35~, K ~\le 15~
• Subtask ~2~ (~66~%): Không có thêm giới hạn của ~N~, ~K~ và ~A_{i}~

Sample Input 1

3 2
120
36
100

Sample Output 1

20

Sample Input 2

5 3
42
20
30
111
63

Sample Output 2

3