Farmer John בונה גינה יפה וצריך להעביר הרבה אדמה.

הגינה היא רצף $N$ ערוגות ($1 \le N \le 100$). ערוגה $i$ מכילה בתחילה $A_{i}$ יחידות אדמה והוא רוצה $B_{i}$. כל $A_{i}$ ו-$B_{i}$ שלמים בטווח $0..10$.

אפשר לקנות יחידה ולשים בערוגה לבחירה בעלות $X$, להסיר יחידה מערוגה לבחירה ולשלוח אותה בעלות $Y$, או להעביר יחידה מ-$i$ ל-$j$ בעלות $Z$ כפול $|i-j|$. חשבו את העלות הכוללת המזערית.

קלט

• שורה 1: שלמים ברווחים $N$, $X$, $Y$, $Z$; $0 \le X, Y, Z \le 1000$.
• שורות $2..1+N$: שורה $i+1$ מכילה $A_{i}$ ו-$B_{i}$ ברווח.

פלט

• שורה 1: שלם, העלות המזערית של הפרויקט.

דוגמאות

קלט 1

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

פלט 1

210

הערה

ארבע ערוגות בשורה מכילות 1, 2, 3, 4 יחידות ויש לשנות ל-4, 3, 2, 0. עלויות הוספה, הסרה והעברה הן 100, 200, 1.

יש להסיר יחידה מערוגה 4 בעלות 200. השאר ניתן להעביר בעלות 10: שלוש יחידות מ-4 ל-1 ואחת מ-3 ל-2.

קרדיט לבעיה: Brian Dean, 2012