Quizá conozcas Goldilocks y los tres osos. Después se hizo agricultora, con $N$ vacas ($(1 \le N \le 20,000)$) en su establo, sensibles a la temperatura.

La vaca $i$ prefiere $A(i)..B(i)$ ($0 \le A(i) \le B(i) \le 10^9$). Con $T < A(i)$ tiene frío y produce $X$; con $T$ dentro ($A(i) \le T \le B(i)$) está cómoda y produce $Y$; con $T > B(i)$ tiene calor y produce $Z$. $Y$ siempre supera $X$ y $Z$.

Con $X$, $Y$, $Z$ y los rangos, calcula la leche máxima con termostato óptimo. $X$, $Y$, $Z$ son enteros en 0..1000 y la temperatura puede ser cualquier entero.

Entrada

• Línea 1: cuatro enteros $N$ $X$ $Y$ $Z$ separados por espacios.
• Líneas $2..1+N$: la línea $1+i$ contiene enteros $A(i)$ y $B(i)$ separados por espacio.

Salida

• Línea 1: leche máxima con temperatura óptima.

Ejemplos

Entrada 1

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

Salida 1

31

Nota

Cuatro rangos: 5..8, 3..4, 13..20, 7..10. Una fría da 7, cómoda 9, caliente 6 unidades.

A 7 u 8, #1 y #4 cómodas, #2 caliente y #3 fría, total 31.

Subtareas

Puntuación parcial: de 10 casos, en 1..4 todos los $B(i) \le 100$, y en 1..6 $N$ es como máximo 1000.

Autor del problema: Brian Dean, 2013