Vielleicht kennst du Goldilocks und die drei Bären. Später wurde sie Bäuerin und hat $N$ Kühe ($(1 \le N \le 20,000)$) im Stall, die temperaturempfindlich sind.

Kuh $i$ mag $A(i)..B(i)$ ($0 \le A(i) \le B(i) \le 10^9$). Bei $T < A(i)$ ist es zu kalt und sie gibt $X$; bei $T$ darin ($A(i) \le T \le B(i)$) angenehm und $Y$; bei $T > B(i)$ zu heiß und $Z$ Einheiten Milch. $Y$ ist immer größer als $X$ und $Z$.

Berechne aus $X$, $Y$, $Z$ und den Bereichen die maximale Milch bei optimalem Thermostat. $X$, $Y$, $Z$ sind ganze Zahlen in 0..1000, die Temperatur darf jede ganze Zahl sein.

Eingabe

• Zeile 1: vier durch Leerzeichen getrennte ganze Zahlen $N$ $X$ $Y$ $Z$.
• Zeilen $2..1+N$: Zeile $1+i$ enthält durch Leerzeichen getrennte ganze Zahlen $A(i)$ und $B(i)$.

Ausgabe

• Zeile 1: maximale Milch bei optimaler Temperatur.

Beispiele

Eingabe 1

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

Ausgabe 1

31

Hinweis

Vier Bereiche: 5..8, 3..4, 13..20, 7..10. Kalt gibt 7, angenehm 9, heiß 6 Einheiten.

Bei 7 oder 8 fühlen #1 und #4 sich wohl, #2 ist zu heiß, #3 zu kalt, insgesamt 31.

Teilaufgaben

Teilpunkte: Von 10 Tests haben 1..4 überall $B(i) \le 100$, und in 1..6 ist $N$ höchstens 1000.

Aufgabenautor: Brian Dean, 2013