Ở đất nước Yên Bình có mỏ vàng dọc theo bờ của dòng sông và mỏ vàng thứ có thể khai thác được tấn vàng. Để phục vụ khai thác vàng, người ta cần hợp nhất và phân phối lại các mỏ vàng sao cho có đúng đống vàng để di chuyển vàng khai thác, ở các mỏ vàng có thể di chuyển được bằng xe tải theo quy tắc sau:
Có thể di chuyển vàng ở hai mỏ vàng bất kì cho nhau với điều kiện ;
Khi di chuyển số vàng từ vị trí sang vị trí hoặc là di chuyển hết số vàng qua hoặc là không di chuyển vàng tại ;
Để di chuyển tấn vàng từ vị trí đến vị trí thì phải mất chi phí .
Yêu cầu: cho và số lượng vàng được khai thác tại mỗi mỏ. Tính chi phí bé nhất để di chuyển số vàng.
Dữ liệu vào:
Dòng đầu ghi hai số ;
dòng tiếp theo mỗi dòng ghi hai giá trị và tương ứng với vị trí và số lượng vàng khai thác được tại mỏ thứ .
Dữ liệu ra:
Ghi ra giá trị bé nhất để hợp nhất số vàng khai thác được di chuyển về đống vàng.
