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.

Biển Nhật Lệ - TP Đồng Hới được nhiều du khách biết đến như một trong những điểm nghỉ ngơi lý tưởng và được tạp chí Forbes (Mỹ) bình chọn là một trong những bãi biển đẹp nhất thế giới. Các bãi tắm có độ dốc lớn, nước trong xanh thích hợp cho những du khách muốn thưởng thức những loại hình dịch vụ giải trí nghỉ dưỡng câu cá, lướt ván, lặn, ngắm san hô…
Trong một đợt đi du lịch ở TP Đồng Hới, sáng sớm Đông thường đi dạo dọc bờ biển Nhật Lệ và nhặt những vỏ ốc rồi xâu chúng lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của Đông như sau: Ban đầu chuỗi ốc rỗng, không có vỏ ốc, khi gặp một vỏ ốc mới có thể lấy để xâu vào 1 trong hai đầu của chuỗi hoặc bỏ đi không lấy, cuối cùng nhận được một chuỗi vỏ ốc mà tính từ đầu đến cuối chuỗi các vỏ ốc có kích thước tăng dần và gồm càng nhiều vỏ ốc càng tốt.
Yêu cầu: Cho trước dãy a1, a2,…,aN là kích thước các vỏ ốc mà Đông lần lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được nhiều vỏ ốc nhất.
Dữ liệu vào: Cho trong file văn bản có tên SEASNAIL.INP có cấu trúc:
   Dòng 1:  Chứa số nguyên dương N (N≤105).
   Dòng 2: Chứa N số nguyên dương a1, a2,…,aN (ai≤109). 
(Các số được ghi cách nhau ít nhất 1 dấu cách)
Dữ liệu ra: Ghi vào file văn bản có tên SEASNAIL.OUT với cấu trúc.
   Dòng 1: Ghi một số nguyên duy nhất là số lượng vỏ ốc trong chuỗi tạo được:
Ví dụ:
SEASNAIL.INP    
5
4   4   5   3   1
SEASNAIL.OUT
4