Forse conoscete Goldilocks e i tre orsi. Poi è diventata contadina, con $N$ mucche ($(1 \le N \le 20,000)$) nella stalla, sensibili alla temperatura.

La mucca $i$ preferisce $A(i)..B(i)$ ($0 \le A(i) \le B(i) \le 10^9$). Con $T < A(i)$ ha freddo e produce $X$; con $T$ dentro ($A(i) \le T \le B(i)$) è comoda e produce $Y$; con $T > B(i)$ ha caldo e produce $Z$. $Y$ supera sempre $X$ e $Z$.

Con $X$, $Y$, $Z$ e intervalli, calcolate il latte massimo con termostato ottimo. $X$, $Y$, $Z$ sono interi in 0..1000 e la temperatura può essere qualsiasi intero.

Input

• Riga 1: quattro interi $N$ $X$ $Y$ $Z$ separati da spazi.
• Righe $2..1+N$: la riga $1+i$ contiene interi $A(i)$ e $B(i)$ separati da spazio.

Output

• Riga 1: latte massimo con temperatura ottima.

Esempi

Input 1

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

Output 1

31

Spiegazione

Quattro intervalli: 5..8, 3..4, 13..20, 7..10. Fredda dà 7, comoda 9, calda 6 unità.

A 7 o 8, #1 e #4 sono comode, #2 calda e #3 fredda, totale 31.

Punteggio

Punti parziali: dei 10 test, in 1..4 tutti i $B(i) \le 100$, e in 1..6 $N$ è al massimo 1000.

Autore del problema: Brian Dean, 2013