Background

This problem has the same statement as the problem of the same name in the 2016 Open Contest Platinum, with the only difference being the testdata constraints.

Problem 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