#1208. PAY - Mua hàng

Bộ nhớ: 256 MiB Thời gian: 1000 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

Nguồn: Ôn Thầy Hiếu Hưng Yên - T11/2019

Siêu thị bán hàng qua mạng VMART có rất nhiều chi nhánh phục vụ và có nhiều phương tiện giao hàng tiên tiến nhanh chóng. Nhân dịp quốc khánh 2/9 , siêu thị đưa ra rất nhiều ưu đãi, khuyến mãi hấp dẫn, đặc biệt với những người mua hàng trực tuyến. An vừa vào trang web của hệ thống cửa hàng và chọn được n mặt hàng đưa vào danh sách các thứ sẽ mua. Món hàng thứ i có giá a_i\ (1≤i≤n) . Khi An chuẩn bị chuyển danh sách hàng đã chọn vào giỏ mua thì xuất hiện một thông báo khuyến mãi mới. Khi khách hàng thanh toán giỏ hàng từ k mặt hàng trở lên, khách hàng sẽ được miễn phí mặt hàng có giá trị nhỏ nhất. An không thể thay đổi thứ tự hàng trong danh sách đã đăng ký mua nhưng có thể cắt danh sách thành các phần, mỗi phần gồm một dãy liên tiếp các hàng trong danh sách và bỏ vào một giỏ hàng riêng thanh toán để nhận được chính sách ưu đãi của siêu thị.

Yêu cầu: Hãy giúp An lựa chọn cách chia thành các giỏ để tổng chi phí phải trả cho n mặt hàng là nhỏ nhất.

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,1≤i≤n) .

Dữ liệu ra:

  • Ghi ra một số nguyên là số tiền ít nhất An cần thanh toán.

Ví dụ:

Dữ liệu vào:
5 2
2 3 1 4 6
Dữ liệu ra:
10

Giới hạn:

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