Vous connaissez peut-être Goldilocks et les trois ours. Elle est ensuite devenue agricultrice et possède $N$ vaches ($(1 \le N \le 20,000)$) dans sa grange, sensibles à la température.

La vache $i$ préfère $A(i)..B(i)$ ($0 \le A(i) \le B(i) \le 10^9$). À $T < A(i)$, elle a froid et produit $X$ ; à $T$ dans l’intervalle ($A(i) \le T \le B(i)$), elle est à l’aise et produit $Y$ ; à $T > B(i)$, elle a chaud et produit $Z$. $Y$ est toujours supérieur à $X$ et $Z$.

Avec $X$, $Y$, $Z$ et les intervalles, calculez le lait maximal par un thermostat optimal. $X$, $Y$, $Z$ sont entiers dans 0..1000, et la température peut être tout entier.

Entrée

• Ligne 1 : quatre entiers $N$ $X$ $Y$ $Z$ séparés par des espaces.
• Lignes $2..1+N$ : la ligne $1+i$ contient les entiers $A(i)$ et $B(i)$ séparés par un espace.

Sortie

• Ligne 1 : le lait maximal avec la température optimale.

Exemples

Entrée 1

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

Sortie 1

31

Remarque

Quatre intervalles : 5..8, 3..4, 13..20, 7..10. Une vache froide produit 7, à l’aise 9, chaude 6 unités.

À 7 ou 8, #1 et #4 sont à l’aise, #2 a chaud et #3 froid, pour 31 unités.

Sous-tâches

Points partiels : parmi 10 tests, dans 1..4 tous les $B(i) \le 100$, et dans 1..6 $N$ vaut au plus 1000.

Auteur du problème : Brian Dean, 2013