Cơ quan hàng không vũ trụ Mĩ NASA vừa thực hiện thành công một dự án lớn. Đó là xây dựng một trạm vũ trụ trên mặt trăng. Công việc trước mắt là duy trì trạm vũ trụ này trong ngày. Để vận hành tốt, lúc nào cũng cần có một phi hành gia ở trên trạm vũ trụ. Tuy nhiên, mỗi phi hành gia không thể ở trên trạm vũ trụ quá ngày liên tiếp, vì vậy NASA cần lập một kế hoạch luân phiên các nhà du hành vũ trụ. Chi phí cho việc luân phiên này cũng khác nhau đối với mỗi ngày và NASA muốn tối thiểu tổng chi phí này. Nhiệm vụ của bạn là đọc các thông tin và đưa ra một kế hoạch tối ưu. Chú ý rằng ở ngày thứ luôn cần có sự thay đổi.
Dữ liệu vào:
Dòng thứ nhất ghi hai số và ;
Dòng thứ trong dòng sau ghi số chi phí cho việc thay đổi nhà du hành vũ trụ trong ngày thứ .
Dữ liệu ra:
Ghi ra một dòng duy nhất chứa số là chi phí tối thiểu cho việc duy trì trạm vũ trụ.
