VMGOLD - Mỏ vàng

Giới hạn
  • Thời gian: 2.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 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 35 3
42
20
30
111
63
Output 2:
3

  • Người up: voj
  • Nguồn bài: VNOI Marathon 2014