Câu 1. Mua hàng (6 điểm).                                           
Một cửa hàng có N món hàng được bày bán trên quầy theo thứ tự từ trái sang phải, với số hiệu lần lượt từ 1..N. Món hàng thứ i có giá tiền là Ai. 
Nhân dịp trung thu, chủ cửa hàng quyết định thực hiện chính sách giảm giá. Cụ thể với món hàng thứ i, gọi B là mảng giá tiền của các món hàng còn trên quầy nằm bên trái i có giá tiền rẻ hơn Ai , sau khi sắp xếp B tăng dần, nếu số lượng phần tử của B không nhỏ hơn K thì có thể mua món hàng i với giá BK. Ngược lại, nếu số lượng phần tử của B nhỏ hơn K thì món hàng i sẽ vẫn giữ giá cũ. Một món hàng khi được bán thì sẽ được đem đi khỏi quầy.
An là một người đam mê mua sắm. An đứng đây từ chiều và muốn mua hết tất cả các món hàng. Thật may mắn cho anh là ngoài An ra không ai mua cả, nên An có thể tự do chọn mua món hàng nào trước mà không sợ món hàng bị mua mất. Tuy nhiên, An vẫn là người chi tiêu hợp lý, anh muốn mua hết tất cả món hàng với số tiền bỏ ra là ít nhất. 
Hãy tính số tiền nhỏ nhất mà An bỏ ra để mua hết tất cả món hàng. 
Dữ liệu vào: Cho trong file văn bản có tên SALE.INP có cấu trúc:
   Dòng 1: Chứa 2 số nguyên dương N và K (1 ≤ N ≤ 3000; 1 ≤ K ≤ N ).
   Dòng 2: Chứa N số nguyên dương Ai là giá tiền của món hàng thứ i (1 ≤ Ai ≤ 109 ).
(Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách)
Dữ liệu ra: Ghi vào file văn bản có tên SALE.OUT với cấu trúc:
   Dòng 1: Ghi số tiền nhỏ nhất mà An phải trả để mua hết tất cả các món hàng.
Ví dụ:  
SALE.INP    
5 4
4 5 3 1 2

SALE.OUT
15
Quy trình tính toán chi tiết:
Món thứ 5 (giá 2):

Các món bên trái có giá nhỏ hơn 2: [1] → Chỉ có 1 món nhỏ hơn.

Không đủ K món nhỏ hơn (K = 4), nên giá không thay đổi → giá = 2.

Món thứ 4 (giá 1):

Không có món nào bên trái có giá nhỏ hơn 1.

Không đủ K món nhỏ hơn (K = 4), nên giá không thay đổi → giá = 1.

Món thứ 3 (giá 3):

Các món bên trái có giá nhỏ hơn 3: [1, 2] → Có 2 món nhỏ hơn.

Không đủ K món nhỏ hơn (K = 4), nên giá không thay đổi → giá = 3.

Món thứ 2 (giá 5):

Món thứ 1 có giá 4, nhỏ hơn giá 5.

Chỉ có 1 món nhỏ hơn 5 → Không đủ K món nhỏ hơn (K = 4), nên giá không thay đổi → giá = 5.

Món thứ 1 (giá 4):

Không có món nào bên trái có giá nhỏ hơn 4.

Không đủ K món nhỏ hơn (K = 4), nên giá không thay đổi → giá = 4.

Tổng chi phí:
Món thứ 5: 2

Món thứ 4: 1

Món thứ 3: 3

Món thứ 2: 5

Món thứ 1: 4

Tổng chi phí = 2 + 1 + 3 + 5 + 4 = 15

Kết quả:
Số tiền An phải trả để mua tất cả các món hàng là 15.

Lý do:
Mỗi món chỉ có giá giảm khi có ít nhất K món nhỏ hơn nó bên trái, nếu không đủ thì giữ nguyên giá ban đầu.