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ô (batch), 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 số nguyên .
Dòng thứ hai chứa số nguyên .
dòng tiếp theo, mỗi dòng chứa một cặp số nguyên dương và , lần lượt biểu thị thời gian cần thiết để hoàn thành riêng nhiệm vụ thứ và hệ số chi phí của nó.
