P3049 [USACO12MAR] Landscaping S

*This problem has the same statement as the [problem of the same name in the 2016 Open Contest Platinum](/problem/P2748), with the only difference being the testdata constraints.*

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.

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 the minimum cost to move the soil.

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