Farmer John xây vườn đẹp và cần chuyển nhiều đất.

Vườn là dãy $N$ luống hoa ($1 \le N \le 100$). Luống $i$ ban đầu có $A_{i}$ đơn vị đất và cần thành $B_{i}$. Mọi $A_{i}$, $B_{i}$ là số nguyên trong $0..10$.

Anh có thể mua một đơn vị và đặt vào luống tùy chọn với giá $X$, lấy một đơn vị từ luống tùy chọn và chở đi với giá $Y$, hoặc chuyển một đơn vị từ $i$ sang $j$ với giá $Z$ nhân $|i-j|$. Tính tổng chi phí nhỏ nhất.

Dữ liệu vào

• Dòng 1: các số nguyên cách nhau bởi dấu cách $N$, $X$, $Y$, $Z$; $0 \le X, Y, Z \le 1000$.
• Các dòng $2..1+N$: dòng $i+1$ chứa $A_{i}$, $B_{i}$ cách nhau bởi dấu cách.

Dữ liệu ra

• Dòng 1: số nguyên là chi phí nhỏ nhất của dự án.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

210

Ghi chú

Bốn luống trong hàng có 1, 2, 3, 4 đơn vị, cần thành 4, 3, 2, 0. Giá thêm, bỏ, chuyển là 100, 200, 1.

Phải bỏ một đơn vị từ luống 4 tốn 200. Còn lại chuyển tốn 10: ba đơn vị từ 4 sang 1 và một từ 3 sang 2.

Ghi công bài toán: Brian Dean, 2012