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 , 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 mặt hàng đưa vào danh sách các thứ sẽ mua. Món hàng thứ có giá . 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ừ 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 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 và ;
Dòng thứ hai chứa số nguyên dương .
Dữ liệu ra:
Ghi ra một số nguyên là số tiền ít nhất An cần thanh toán.
