Description

Farmer John (FJ) plans to build a garden and needs to move quite a bit of soil.

The garden consists of $N$ flowerbeds ($1 \leq N \leq 100$), where flowerbed $i$ contains $A_i$ units of soil. FJ wants flowerbed $i$ to contain $B_i$ units of soil, and it is guaranteed that $0 \leq A_i, B_i \leq 10$.

To achieve this goal, he can do the following:

• Buy one unit of soil and place it in a specified flowerbed, at a cost of $X$.
• Remove one unit of soil from any flowerbed, at a cost of $Y$.
• Transport one unit of soil from flowerbed $i$ to flowerbed $j$, at a cost of $Z|i-j|$.

Please help FJ compute the minimum cost to move the soil.

Input Format

The first line contains four integers $N, X, Y, Z$ ($0 \leq X, Y, Z \leq 1000$).

The next $N$ lines each contain two integers $A_i, B_i$ for the $i$-th line.

Output Format

Output the minimum cost to move the soil.

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

210 

Hint

With the following plan, the minimum cost is $210$, and you can prove that no cheaper plan exists.

• Remove one unit of soil from flowerbed $4$, costing $200$.
• Move three units of soil from flowerbed $4$ to flowerbed $1$, costing $3 \times 3=9$.
• Move one unit of soil from flowerbed $3$ to flowerbed $2$, costing $1 \times 1=1$.

Translated by ChatGPT 5