نسمي الرسم البياني غير الموجه المتصل، الخالي من الحلقات الذاتية والحواف المتعددة، رسمًا صباريًا إذا وفقط إذا كانت كل حافة تنتمي إلى دورة بسيطة واحدة على الأكثر. والدورة البسيطة هي دورة لا تمر بأي رأس أكثر من مرة.

رسم صباري؛ ليس صباريًا لأن الحافة الوسطى تقع على دورتين؛ ليس صباريًا لأنه غير متصل.

معطاة $n$ نقطة في المستوى، وإحداثيا النقطة $i$ هما $(x_i,y_i)$. ومعطاة $m$ حافة، تصل الحافة $i$ بين الرأسين $u_i,v_i$. نضمن أن الرسم البياني غير الموجه المكوّن من هذه النقاط والحواف رسم صباري.

في البداية تكون الحواف $m$ كلها بيضاء. يمكنك اختيار بعض الحواف وتلوينها بالأسود، وتكلفة تلوين الحافة $i$ بالأسود هي $w_i$.

لكل زوج من الحواف المختلفة اللون التي تشترك في رأس، إذا أمكن الوصول من الحافة البيضاء إلى الحافة السوداء بالدوران عكس اتجاه عقارب الساعة حول الرأس المشترك بمقدار $x$ حافة، تحصل على طاقة قدرها $p\times x$. وبصورة خاصة، إذا كانت حافتان على استقامة واحدة وفي الاتجاه نفسه، أي إن للرأس الآخر في كل منهما الزاوية القطبية نفسها بالنسبة إلى الرأس المشترك، فنفترض الوصول أولًا إلى الحافة ذات الرقم الأصغر؛ أي نعد زاويتها القطبية أصغر.

أوجد أكبر قيمة لمجموع الطاقة المكتسبة بعد التلوين ناقص مجموع تكاليف التلوين.

الإدخال

تُقرأ البيانات من الملف color.in.

يحتوي السطر الأول على ثلاثة أعداد صحيحة موجبة $n,m,p$ تمثل عدد الرؤوس وعدد الحواف ومعامل الطاقة، على الترتيب.

تحتوي الأسطر $m$ التالية على ثلاثة أعداد صحيحة $u_i,v_i,w_i$ في السطر $i$، تصف طرفي الحافة $i$ وتكلفتها.

تحتوي الأسطر $n$ التالية على عددين صحيحين $x_i,y_i$ في السطر $i$، وهما إحداثيا النقطة $i$.

الإخراج

اكتب الناتج في الملف color.out.

اطبع عددًا صحيحًا واحدًا في سطر واحد: أكبر قيمة لمجموع الطاقة المكتسبة بعد التلوين ناقص مجموع تكاليف التلوين.

أمثلة

الإدخال 1

5 4 10
1 4 1
2 3 2
3 4 2
3 5 2
0 1
1 1
0 0
1 0
2 0

الإخراج 1

38

ملاحظة

في الشكل التالي تمثل الخطوط السوداء المتصلة الحواف الملوّنة بالأسود، وتمثل الخطوط الرمادية المنقطة الحواف التي بقيت بيضاء.

بعد دفع تكلفة $2$ لتلوين $(3,4)$ بالأسود، يمكن الوصول من $(1,4)$ إلى $(3,4)$ بالدوران عكس عقارب الساعة حول الرأس $4$ بمقدار حافة واحدة، فنحصل على طاقة $10\times1=10$. ويمكن الوصول من $(2,3)$ إلى $(3,4)$ بالدوران عكس عقارب الساعة حول الرأس $3$ بمقدار حافة واحدة، فنحصل على طاقة $10\times1=10$؛ لاحظ أن القاعدة في وصف المسألة تجعلنا نصل إلى $(3,4)$ قبل $(3,5)$. ويمكن الوصول من $(3,5)$ إلى $(3,4)$ بالدوران عكس عقارب الساعة حول الرأس $3$ بمقدار حافتين، فنحصل على طاقة $10\times2=20$. لذا يكون مجموع الطاقة $10+10+20=40$، ومجموع التكلفة $2$، والقيمة القصوى المطلوبة $40-2=38$. ويمكن إثبات عدم وجود تلوين يعطي قيمة أكبر.

المثال 2

انظر الملفين color/color2.in وcolor/color2.ans في دليل المتسابق.

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

نضمن في جميع بيانات الاختبار ما يلي:

• $2\le n,m\le2\times10^5$، و$1\le p\le1000$؛
• $\forall1\le i\le m,\ 1\le u_i,v_i\le n,\ 0\le w_i\le10^4$؛
• $\forall1\le i\le n,\ 0\le x_i,y_i\le10^7$؛
• الرسم البياني المعطى صباري؛
• لا تتطابق إحداثيات أي نقطتين.

الخاصية A: نضمن أن $m=n-1$، أي إن الرسم البياني المعطى شجرة.

الخاصية B: نضمن أن أي حافتين لا تشتركان في رأس لا تتقاطعان في المستوى، أي إن الرسم البياني المعطى مضمّن في المستوى.

الخاصية C: نضمن أن $\forall1\le i\le m,\ w_i=0$.

الخاصية D: نضمن أن $\forall1\le i\le m,\ w_i=1$، وأن $p=1$.