אולי שמעתם על Goldilocks ושלושת הדובים. אחר כך הפכה לחקלאית עם $N$ פרות ($(1 \le N \le 20,000)$) ברפת, הרגישות לטמפרטורה.

פרה $i$ מעדיפה $A(i)..B(i)$ ($0 \le A(i) \le B(i) \le 10^9$). ב־$T < A(i)$ קר לה והיא נותנת $X$; ב־$T$ בטווח ($A(i) \le T \le B(i)$) נוח והיא נותנת $Y$; ב־$T > B(i)$ חם והיא נותנת $Z$. תמיד $Y$ גדול מ־$X$ ומ־$Z$.

מ־$X$, $Y$, $Z$ והטווחים חשבו את החלב המרבי בתרמוסטט מיטבי. $X$, $Y$, $Z$ שלמים ב־0..1000, והטמפרטורה יכולה להיות כל שלם.

קלט

• שורה 1: ארבעה שלמים $N$ $X$ $Y$ $Z$ מופרדים ברווחים.
• שורות $2..1+N$: שורה $1+i$ מכילה שלמים $A(i)$ ו־$B(i)$ מופרדים ברווח.

פלט

• שורה 1: החלב המרבי בטמפרטורה מיטבית.

דוגמאות

קלט 1

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

פלט 1

31

הסבר

ארבעה טווחים: 5..8, 3..4, 13..20, 7..10. קרה נותנת 7, נוחה 9, חמה 6 יחידות.

ב־7 או 8 נוח ל־#1 ול־#4, חם ל־#2 וקר ל־#3, סך 31.

ניקוד

ניקוד חלקי: מ־10 המקרים, ב־1..4 כל $B(i) \le 100$, וב־1..6 $N$ לכל היותר 1000.

מחבר הבעיה: Brian Dean, 2013