Farmer John construit un beau jardin et doit déplacer beaucoup de terre.

Le jardin est une suite de $N$ plates-bandes ($1 \le N \le 100$). La plate-bande $i$ contient initialement $A_{i}$ unités de terre et doit en contenir $B_{i}$. Tous les $A_{i}$ et $B_{i}$ sont des entiers dans $0..10$.

Il peut acheter une unité et la placer où il veut pour $X$, retirer et expédier une unité de son choix pour $Y$, ou transporter une unité de $i$ à $j$ pour $Z$ fois $|i-j|$. Calculez le coût total minimal.

Entrée

• Ligne 1 : entiers séparés par des espaces $N$, $X$, $Y$, $Z$ ; $0 \le X, Y, Z \le 1000$.
• Lignes $2..1+N$ : la ligne $i+1$ contient $A_{i}$ et $B_{i}$ séparés par un espace.

Sortie

• Ligne 1 : un entier, le coût minimal du projet.

Exemples

Entrée 1

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

Sortie 1

210

Remarque

Quatre plates-bandes en ligne contiennent 1, 2, 3, 4 unités et doivent passer à 4, 3, 2, 0. Ajouter, retirer, transporter coûte 100, 200, 1.

Une unité est retirée de la plate-bande 4 pour 200. Le reste se déplace pour 10 : trois unités de 4 à 1 et une de 3 à 2.

Crédits du problème : Brian Dean, 2012