تريد نملة تقطع 1 كم في 100 دقيقة الانتقال من نقطة بداية إلى وجهة على سهل عظيم. يجب أن تتحرك موازية لمحوري $x$ و$y$، وقد يستغرق التحرك في المناطق التلية وقتًا أطول. عند إعطائك البداية والوجهة والمناطق التلية والزمن اللازم لقطع 1 كم في كل منها، احسب أقل زمن لوصول النملة إلى الوجهة.

كل منطقة تلية مستطيل أضلاعه موازية لمحوري $x$ و$y$، وله زمن محدد لقطع كل كيلومتر. ينطبق هذا الزمن على داخل المستطيل فقط وليس على حدوده. لا يتداخل أي مستطيلين. إحداثيات $x$ للبداية والوجهة ورؤوس المستطيلات المختلفة أعداد صحيحة ولا تتطابق، وينطبق الأمر نفسه على إحداثيات $y$. تقع البداية والوجهة دائمًا خارج المستطيلات.

يستخدم الشكل أعلاه إحداثيات بالكيلومترات. ويُظهر مستطيلًا زاويته السفلية اليسرى $(0,1)$ والعلوية اليمنى $(5,2)$ وزمنه 200 دقيقة لكل كيلومتر، ومستطيلًا زاويته السفلية اليسرى $(4,3)$ والعلوية اليمنى $(9,4)$ وزمنه 1000 دقيقة لكل كيلومتر. وتظهر أسرع المسارات من $A$ إلى $B$ ومن $C$ إلى $D$، وزمناهما الأدنيان 700 و1000 دقيقة على الترتيب.

يجب أن تنفّذ الدالة التالية.

long long shortest_path(pair<int, int> src, pair<int, int> dst,
                        vector<pair<int, int>> p1, vector<pair<int, int>> p2,
                        vector<int> w);

تُستدعى هذه الدالة مرة واحدة فقط. src وdst هما البداية والوجهة. تُعطى الزاوية السفلية اليسرى لكل مستطيل في p1 والعلوية اليمنى في p2. باستخدام القيم المعطاة، أعد أقل زمن للانتقال من src إلى dst.

تفاصيل التنفيذ

يجب أن ترسل ملفًا واحدًا اسمه plain.cpp ينفّذ الدالة التالية.

long long shortest_path(pair<int, int> src, pair<int, int> dst,
                        vector<pair<int, int>> p1, vector<pair<int, int>> p2,
                        vector<int> w);

يجب أن تعمل الدالة كما وُصف أعلاه. يمكنك إنشاء دوال أخرى للاستخدام الداخلي. يجب ألا يجري الكود المرسل إدخالًا أو إخراجًا وألا يصل إلى ملفات أخرى.

برنامج التقييم النموذجي

يقرأ برنامج التقييم المرفق الإدخال بالصيغة التالية. إحداثيات $x,y$ بوحدة الكيلومتر.

السطر الأول: $N\ x_s\ y_s\ x_e\ y_e$.

• $N$: عدد المستطيلات.
• $x_s,y_s$: إحداثيا $x,y$ للبداية.
• $x_e,y_e$: إحداثيا $x,y$ للوجهة.

كل سطر من الأسطر $N$ التالية: $x_1\ y_1\ x_2\ y_2\ w$.

• $x_1,y_1$: إحداثيا $x,y$ للزاوية السفلية اليسرى للمستطيل.
• $x_2,y_2$: إحداثيا $x,y$ للزاوية العلوية اليمنى.
• $x_1<x_2$.
• $y_1<y_2$.
• $w$: الزمن بالدقائق لقطع 1 كم داخل المستطيل.

يطبع برنامج التقييم المرفق القيمة التي تعيدها دالتك shortest_path().

القيود

• $1\le N\le100000$
• $100\le w\le10^8$
• $0\le x,y\le10^8$، حيث $x,y$ إحداثيات البداية أو الوجهة أو أحد رؤوس المستطيلات.
• $N,w,x,y$ جميعها أعداد صحيحة.

المهام الفرعية

1. (23 نقطة) $N\le500$
2. (35 نقطة) $N\le5000$
3. (31 نقطة) $x_2-x_1=1$
4. (61 نقطة) لا توجد قيود إضافية.

أمثلة

الإدخال 1

3 2 14 5 1
4 6 6 10 1000
0 7 3 9 200
1 2 8 5 150

الإخراج 1

1750

الإدخال 2

13 0 38 100 25
1 39 2 46 190
9 78 10 80 230
20 42 21 89 170
27 26 28 68 170
35 41 36 99 270
43 36 44 63 280
51 15 52 27 150
57 14 58 29 190
64 2 65 90 160
75 33 76 35 290
78 5 79 100 290
88 28 89 40 190
94 7 95 50 250

الإخراج 2

11770