Có nhiệm vụ được sắp xếp thành một dãy chờ thực hiện trên một máy, thứ tự của chúng không được thay đổi. Máy sẽ chia nhiệm vụ này thành một số lô, mỗi lô bao gồm các nhiệm vụ liên tiếp nhau. Bắt đầu từ thời điểm , các nhiệm vụ được gia công theo từng lô. Thời gian cần thiết để thực hiện nhiệm vụ thứ là . Ngoài ra, trước khi bắt đầu mỗi lô nhiệm vụ, máy cần thời gian khởi động là . Do đó, thời gian cần thiết để thực hiện một lô nhiệm vụ là thời gian khởi động cộng với tổng thời gian thực hiện của từng nhiệm vụ trong lô đó.
Sau khi một nhiệm vụ được thực hiện xong, nó sẽ chờ trong máy cho đến khi toàn bộ nhiệm vụ trong cùng lô đó hoàn thành. Nghĩa là, các nhiệm vụ trong cùng một lô sẽ hoàn thành tại cùng một thời điểm. Chi phí của mỗi nhiệm vụ được tính bằng thời điểm hoàn thành của nó nhân với một hệ số chi phí .
Hãy lập kế hoạch phân nhóm cho máy sao cho tổng chi phí là nhỏ nhất.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên, lần lượt là .
dòng tiếp theo, mỗi dòng chứa hai số nguyên .
Kết quả:
Một số duy nhất là tổng chi phí nhỏ nhất.
Ví dụ:
Dữ liệu:
5
1
1 3
3 2
4 3
2 3
1 4
Kết quả:
153
Giới hạn: .
Lưu ý rằng mặc dù biểu thị thời gian, nhưng trong bài toán này có thể là số âm.
