Farmer John đang xây dựng một khu vườn được tạo cảnh quan đẹp mắt và cần di chuyển một lượng lớn đất trong quá trình này.

Khu vườn gồm một dãy \(N\) luống hoa (\(1 \leq N \leq 100\,000\)), trong đó ban đầu luống hoa \(i\) chứa \(A_i\) đơn vị đất. Farmer John muốn tạo lại cảnh quan khu vườn sao cho mỗi luống hoa \(i\) chứa \(B_i\) đơn vị đất. Tất cả các giá trị \(A_i\) và \(B_i\) đều là số nguyên trong khoảng \(0 \ldots 10\).

Để tạo cảnh quan cho khu vườn, Farmer John có một số lựa chọn: ông có thể mua một đơn vị đất và đặt nó vào một luống hoa tùy chọn với chi phí \(X\) đơn vị tiền; ông có thể lấy một đơn vị đất ra khỏi một luống hoa tùy chọn rồi chuyển nó đi nơi khác với chi phí \(Y\) đơn vị tiền; hoặc ông có thể vận chuyển một đơn vị đất từ luống hoa \(i\) đến luống hoa \(j\) với chi phí bằng \(Z\) nhân với \(|i-j|\). Hãy tính tổng chi phí nhỏ nhất để Farmer John hoàn thành dự án tạo cảnh quan.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(X\), \(Y\) và \(Z\) (\(0 \leq X, Y \leq 10^8\); \(0 \leq Z \leq 1000\)). Dòng \(i+1\) chứa hai số nguyên \(A_i\) và \(B_i\).

Dữ liệu ra

In ra tổng chi phí nhỏ nhất mà FJ cần bỏ ra để tạo cảnh quan.

Ví dụ

4 100 200 1
1 4
2 3
3 2
4 0

210

Lưu ý rằng bài này đã từng xuất hiện trong một kỳ thi USACO trước đây ở bảng Silver; tuy nhiên, các giới hạn trong phiên bản hiện tại đã được tăng lên đáng kể, vì vậy không nên kỳ vọng lời giải cho phiên bản trước, dễ hơn sẽ đạt được nhiều điểm.

Nguồn

USACO 2016 US Open Contest, Platinum - Landscaping: https://usaco.org/index.php?page=viewproblem2&cpid=650

Tác giả: Brian Dean.