Farmer John baut einen schön gestalteten Garten und muss viel Erde bewegen.

Der Garten ist eine Reihe von $N$ Beeten ($1 \le N \le 100$). Beet $i$ hat anfangs $A_{i}$ Erdeinheiten und soll $B_{i}$ haben. Alle $A_{i}$ und $B_{i}$ sind ganze Zahlen in $0..10$.

Er kann eine Einheit kaufen und beliebig platzieren für $X$, eine Einheit beliebig entfernen und wegschaffen für $Y$, oder eine Einheit von $i$ zu $j$ für $Z$ mal $|i-j|$ transportieren. Berechne die minimalen Gesamtkosten.

Eingabe

• Zeile 1: durch Leerzeichen getrennte ganze Zahlen $N$, $X$, $Y$, $Z$; $0 \le X, Y, Z \le 1000$.
• Zeilen $2..1+N$: Zeile $i+1$ enthält $A_{i}$ und $B_{i}$ mit Leerzeichen.

Ausgabe

• Zeile 1: eine ganze Zahl, die minimalen Projektkosten.

Beispiele

Eingabe 1

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

Ausgabe 1

210

Hinweis

Vier Beete in einer Reihe haben 1, 2, 3, 4 Einheiten und sollen 4, 3, 2, 0 haben. Hinzufügen, Entfernen und Transport kosten 100, 200, 1.

Eine Einheit aus Beet 4 muss für 200 entfernt werden. Der Rest bewegt sich für 10: drei Einheiten von 4 nach 1 und eine von 3 nach 2.

Aufgabenautor: Brian Dean, 2012