Có \(N\) công việc cần thực hiện trên một máy theo thứ tự từ \(1\) đến \(N\). Bạn chia dãy công việc thành các lô không rỗng; mỗi lô gồm một đoạn công việc liên tiếp. Máy xử lý các lô theo thứ tự của chúng.

Máy bắt đầu hoạt động tại thời điểm \(0\). Trước khi xử lý mỗi lô, máy cần một khoảng thời gian chuẩn bị bằng \(S\), rồi xử lý lần lượt các công việc trong lô. Công việc \(i\) cần thời gian xử lý \(T_i\). Ngay khi toàn bộ lô đã xử lý xong, máy đưa ra đồng thời kết quả của tất cả công việc trong lô. Vì vậy, nếu lô gồm các công việc \(x,x+1,\ldots,x+k\) bắt đầu tại thời điểm \(t\), thời điểm đưa ra kết quả của mỗi công việc trong lô là \(t+S+T_x+T_{x+1}+\cdots+T_{x+k}\). Gọi thời điểm đưa ra kết quả của công việc \(i\) là \(O_i\). Công việc này có hệ số chi phí \(F_i\) và chi phí \(O_iF_i\).

Hãy tìm cách chia lô để tổng chi phí của tất cả công việc nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa \(N\), với \(1\le N\le 10000\).
• Dòng thứ hai chứa \(S\), với \(0\le S\le 50\).
• Mỗi dòng trong \(N\) dòng tiếp theo chứa \(T_i,F_i\) của công việc \(i\), với \(1\le T_i,F_i\le 100\).

Trong mỗi bộ kiểm tra, tổng chi phí của bất kỳ cách chia lô nào cũng không vượt quá \(2^{31}-1\).

Dữ liệu ra

In một số nguyên là tổng chi phí nhỏ nhất.

Chấm điểm

Có 20 bộ kiểm tra, mỗi bộ tương ứng 5 điểm trong thang điểm gốc 100. Một bộ kiểm tra chỉ được điểm khi kết quả đúng và chương trình chạy trong giới hạn thời gian; ngược lại được 0 điểm.

Ví dụ

2
50
100 100
100 100

45000

5
1
1 3
3 2
4 3
2 3
1 4

153

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.