Sau thời gian dài chờ đợi, cuối cùng thì các nồi bánh Chưng của các lớp đã luộc xong. Giờ là đến công đoạn chuyển bánh về xếp gọn lại tại một khu vực.
Có lớp tham gia gói bánh. Tất cả bánh sau khi luộc xong đang được xếp trên một đường thẳng (mà ta coi như một trục tọa độ), lớp thứ có cái và đang xếp ở tọa độ nguyên (như vậy có tất cả cái bánh). Nhà trường muốn chuyển tất cả cái bánh này về xếp thành một đoạn liên tiếp nhau, mỗi cái ở một điểm có tọa độ nguyên. Chi phí vận chuyển một cái bánh từ tọa độ đến tọa độ là .
Yêu cầu: Hãy giúp nhà trường tính toán chi phí tối thiểu để di chuyển tất cả cái bánh.
Dữ liệu vào:
Dòng đầu chứa số nguyên dương ;
dòng tiếp theo, dong thứ chứa hai số nguyên và .
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Dữ liệu ra:
Một số nguyên duy nhất là chi phí tối thiểu để di chuyển tất cả cái bánh.
Ví dụ:
Dữ liệu vào:
2
2 1
1 3
Dữ liệu ra:
1
Giải thích:
Ta chuyển một cái bánh từ tọa độ sang tọa độ mất chi phí là . Lúc này cái bánh được xếp trên các tọa độ .
Giới hạn:
Trong tất cả các test: . Trong đó:
Subtask số test ứng với số điểm có
Subtask số test khác ứng với số điểm có
Subtask số test khác ứng với số điểm có với
Subtask số test còn lại ứng với số điểm không có ràng buộc gì thêm.
