#848. SALEOFF - Khuyến mại

Bộ nhớ: 256 MiB Thời gian: 200 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Vào ngày 9/9 Shopee có đợt siêu khuyến mại với nhiều ưu đãi hấp dẫn. Tèo cũng đang phải tích lũy hàng cho mùa dịch COVID nên đã lên Shopee chọn mua hàng online. Tèo đã chọn được n món hàng cho vào giỏ hàng theo thứ tự từ 1 đến n , món hàng thứ i có giá là a_i . Khi chuẩn bị thanh toán thì Tèo biết được có chương trình khuyến mại: Mỗi đơn hàng thanh toán từ k món hàng trở lên sẽ được khuyến mại món hàng có giá trị nhỏ nhất. Lúc này Tèo không thể thay đổi thứ tự các món hàng trong giỏ hàng mà chỉ có thể tách ra thành các đoạn liên tiếp các món hàng để thành các đơn hàng thanh toán.

Yêu cầu: Do tình hình kinh tế khó khăn nên Tèo rất muốn bạn giúp Tèo tính toán số tiền ít nhất có thể để thanh toán hết giỏ hàng.

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên dương n k ;
  • Dòng thứ hai chứa n số nguyên dương a_1,a_2,…,a_n\ (1≤a_i≤10^9) .

Dữ liệu ra:

  • Một số nguyên duy nhất là tổng số tiền nhỏ nhất để thanh toán hết giỏ hàng.

Ví dụ:

Dữ liệu vào:

5 2
2 3 1 4 6

Dữ liệu ra:

10

Giải thích:

Tèo tách thành các đơn hàng như sau 2, 3 | 1 | 4, 6 .

Giới hạn:

  • 30\% số điểm có n,k≤20 ;
  • 30\% số điểm khác có n,k≤10^3 ;
  • 40\% số điểm còn lại có n,k≤10^5 .