Hình thứ có khoảng ngang ban đầu và được tịnh tiến ngang với chi phí bằng độ dài dịch. Hãy làm hợp của hình liên thông, tương đương mọi cặp khoảng liên tiếp giao nhau, với tổng chi phí nhỏ nhất.
Input
- Dòng đầu chứa .
- dòng tiếp theo chứa và .
Output
- In tổng độ dài tịnh tiến nhỏ nhất.
Constraints
- .
- .
- Các trường hợp ngữ nghĩa quan trọng:
- : . Không cần dịch và chi phí bằng .
- : Các khoảng đã giao nhau liên tiếp. Chi phí tối ưu bằng .
- : Độ rộng các hình khác nhau. Hai phía của cửa sổ chuyển trạng thái dịch khác nhau.
- : Các khoảng cách nhau rất xa. Tổng chi phí cần kiểu bit.
Scoring
- Subtask ( điểm): test đầu có kích thước nhỏ, phù hợp với lời giải vét cạn mô tả trong tài liệu.
- Subtask ( điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
3 1 3 6 8 9 12
Output
4
Giải thích: Dịch hình thứ nhất sang phải đơn vị thành và hình thứ ba sang trái đơn vị thành . Khi đó nối liền với tổng chi phí ; các hai khoảng trống ban đầu cũng cho cận dưới .