Lập kế hoạch theo khối (Batch Scheduling)

Bài toán

Có một chuỗi N công việc cần một chiếc máy thực hiện. Các công việc được đánh số theo thứ tự từ 1 đến N (N). Chuỗi công việc được phân vào một hoặc nhiều khối trong đó mỗi khối chứa một số liên tục công việc liên tục theo đúng thứ tự chuỗi. Quá trình thực hiện công việc bắt đầu từ thời gian 0. Các khối được xử lý lần lượt theo nguyên tắc nếu khối b chứa các công việc với số hiệu nhỏ hơn các công việc ở khối c, thì khối b được xử lý trước khối c. Các công việc trong một khối được thực hiện liên tục. Ngay sau khi thực hiện xong tất cả các công việc trong một khối, máy sẽ đưa ra kết quả thực hiện các công việc đó. Thời gian đưa ra kết quả thực hiện công việc j là thời gian máy xử lý xong khối có chứa công việc j

Gọi S là thời gian máy chuẩn bị để xử lý mỗi khối. Với mỗi công việc i, ta có hệ số chi phí là F_i và thời gian T_i để thực hiện công việc. Nếu một khối gồm các công việc x, x+1,... , x+k và thời gian bắt đầu thực hiện công việc là t, thì tổng thời gian đưa ra kết quả cho mọi công việc trong khối là t + S + (T_x + T_x+1 +... + T_y+-k1 + T_y). Chú ý máy đưa ra kết quả cho tất cả các công việc trong khối cùng một lúc. Nếu thời gian đưa ra kết quả thực hiện công việc i là O_i, thì chi phí thực hiện công việc đó là O_i F_i. Ví dụ, giả sử có 5 công việc, thời gian máy chuẩn bị là S = 1, (T₁, T₂, T₃, T₄, T₅) = (1, 3, 4, 2, 1) và (F₁, F₂, F₃, F₄, F₅) = (3, 2, 3, 3, 4). Nếu 5 công việc trên được chia thành ba khối {1, 2}, {3}, {4, 5}, thì tổng thời gian đưa ra kết quả là (O₁, O₂, O₃, O₄, O₅) = (5, 5, 10, 14, 14) và chi phí để thực hiện tất cả các công việc đó lần lượt là (15, 10, 30, 42, 56). Tổng chi phí để phân chia công việc là tổng chi phí thực hiện tất cả các công việc. Tổng chi phí của ví dụ trên là 153.

Cho trước thời gian chuẩn bị xử lý khối, chuỗi công việc, thời gian thực hiện công việc và hệ số chi phí cho trước, hãy viết chương trình tính tổng chi phí tối thiểu.

INPUT

Dòng đầu tiên chứa số công việc N, 1≤N≤10000. Dòng thứ hai chứa thời gian máy chuẩn bị để xử lý khối, thời gian S này là một số nguyên, 0≤S≤ 50. N dòng tiếp theo chứa thông tin về các công việc theo thứ tự 1, 2,..., N. Số đầu tiên trên mỗi dòng đó là số nguyên T_i, chỉ thời gian máy thực hiện công việc 1≤T_i ≤ 100. Sau đó là một số nguyên F_i, 1 ≤F_i ≤ 100, chỉ hệ số chi phí thực hiện công việc.

OUTPUT

Output là một dòng chứa một số nguyên chỉ tổng chi phí tối thiểu.

Ví dụ

INPUT và OUTPUT

Ví dụ 2 là ví dụ xét đến ở trên.

Chú ý

Với mọi bộ dữ liệu test, tổng chi phí đều không vượt quá 2³¹ - 1.

Cho điểm