Giải bài trực tuyến

            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.

Yêu cầu

            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. 

Giới hạn

      Trong tất cả các test :

• N <= 3000;     
• K <= 100,        K <= N
• 1 <= A_i <= 10¹⁰

      Subtask 1 (33%) : N <= 35,    K <= 15

      Subtask 2 (66%) : Không có giời hạn của N, K và A_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

Example

Input 1:

3 2

120

36

100

Output 1:

20

Input 2:

5 3
5 3

42

20

30

111

63

Output 2:

3
42Output 1:
30
111
63