Może znasz Goldilocks i trzy niedźwiedzie. Potem została farmerką i ma $N$ krów ($(1 \le N \le 20,000)$) w oborze, wrażliwych na temperaturę.

Krowa $i$ lubi $A(i)..B(i)$ ($0 \le A(i) \le B(i) \le 10^9$). Przy $T < A(i)$ jest zimno i daje $X$; przy $T$ w zakresie ($A(i) \le T \le B(i)$) wygodnie i $Y$; przy $T > B(i)$ gorąco i $Z$. $Y$ zawsze przewyższa $X$ i $Z$.

Z $X$, $Y$, $Z$ i zakresów oblicz największy udój przy optymalnym termostacie. $X$, $Y$, $Z$ są całkowite w 0..1000, temperatura może być dowolną całkowitą.

Wejście

• Wiersz 1: cztery całkowite $N$ $X$ $Y$ $Z$ oddzielone spacjami.
• Wiersze $2..1+N$: wiersz $1+i$ zawiera całkowite $A(i)$ i $B(i)$ oddzielone spacją.

Wyjście

• Wiersz 1: największy udój przy optymalnej temperaturze.

Przykład

Wejście 1

4 7 9 6
5 8
3 4
13 20
7 10

Wyjście 1

31

Uwagi

Cztery zakresy: 5..8, 3..4, 13..20, 7..10. Zimna daje 7, wygodna 9, gorąca 6 jednostek.

Przy 7 lub 8 #1 i #4 mają wygodnie, #2 za gorąco, #3 za zimno, suma 31.

Podzadania

Częściowe punkty: z 10 testów w 1..4 wszystkie $B(i) \le 100$, a w 1..6 $N$ najwyżej 1000.

Autor zadania: Brian Dean, 2013