Nước ép hỗn hợp (Mix Juice)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một cửa hàng có $N$ loại trái cây, loại $i$ có giá $p_i$. Bạn phải chọn đúng $K$ loại khác nhau và mua một quả của mỗi loại đã chọn. Hãy tìm tổng tiền nhỏ nhất.

Input

Dòng đầu chứa $N, K$. Dòng thứ hai chứa $N$ số nguyên $p_1,\ldots,p_N$.

Output

In tổng giá nhỏ nhất.

Subtask

Các giới hạn chung:

• $1 \le K \le N \le 1000$.

• $1 \le p_i \le 1000$.

• Subtask 1 (20 điểm): $N \le 20$

• Subtask 2 (30 điểm): $N \le 200$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

5 3
50 100 80 120 80

Output

210

Giải thích

Ba mức giá nhỏ nhất là $50,80,80$, có tổng $210$.