قد تعرف قصة 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