Background

This problem is the same in meaning as the Silver Division problem with the same name from the March 2012 Monthly Contest. The only difference is the constraints.

Problem Description

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.

Input Format

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 Format

Output the minimum cost to move the soil.

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

210

Hint

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