P2748 [USACO16OPEN] Landscaping P

*This problem is the same in meaning as [the Silver Division problem with the same name from the March 2012 Monthly Contest](/problem/P3049). The only difference is the constraints.*

Farmer John plans to build a garden, and he needs to move a lot of soil. The garden consists of $N$ flowerbeds ($1 \leq N \leq 10^5$). Flowerbed $i$ initially contains $A_i$ units of soil. FJ wants flowerbed $i$ to contain $B_i$ units of soil. It is guaranteed that $0 \leq A_i,B_i \leq 10$. To achieve this, he can do the following: - Buy one unit of soil and put it into 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 \leq 10^8$，$0 \leq Z \leq 1000$). The next $N$ lines each contain two integers $A_i,B_i$ on line $i$.

Output the minimum cost to move the soil.

Using the plan below, the minimum cost is $210$. It can be proven that no plan with a smaller cost 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