กราฟไม่มีทิศทางที่เชื่อมต่อกัน ไม่มีลูปและไม่มีเส้นเชื่อมซ้ำ เรียกว่า กราฟแคกตัส ก็ต่อเมื่อเส้นเชื่อมแต่ละเส้นอยู่ในวงจรเชิงเดียวได้ไม่เกินหนึ่งวง โดยวงจรเชิงเดียวคือวงจรที่ไม่ผ่านจุดยอดซ้ำ

ซ้าย: กราฟแคกตัส; กลาง: ไม่ใช่กราฟแคกตัส เพราะเส้นเชื่อมตรงกลางอยู่ในสองวงจร; ขวา: ไม่ใช่กราฟแคกตัส เพราะกราฟไม่เชื่อมต่อกัน

กำหนดจุดบนระนาบ $n$ จุด โดยจุดที่ $i$ มีพิกัด $(x_i,y_i)$ และเส้นเชื่อม $m$ เส้น โดยเส้นเชื่อมที่ $i$ เชื่อมจุดยอด $u_i,v_i$ รับประกันว่ากราฟไม่มีทิศทางที่ประกอบด้วยจุด $n$ จุดและเส้นเชื่อม $m$ เส้นนี้เป็นกราฟแคกตัส

เริ่มต้นเส้นเชื่อมทั้ง $m$ เส้นเป็นสีขาว คุณสามารถเลือกเส้นเชื่อมบางเส้นแล้วระบายเป็นสีดำ โดยค่าใช้จ่ายในการระบายเส้นเชื่อมที่ $i$ เป็นสีดำเท่ากับ $w_i$

สำหรับเส้นเชื่อมต่างสีกันแต่ละคู่ที่มีจุดยอดร่วมกัน สมมติว่าเริ่มจากเส้นเชื่อมสีขาวแล้วหมุนทวนเข็มนาฬิการอบจุดยอดร่วมนั้นไป $x$ เส้นเชื่อมจึงถึงเส้นเชื่อมสีดำ จะได้รับพลังงาน $p\times x$ โดยเฉพาะสำหรับเส้นเชื่อมสองเส้นที่อยู่บนเส้นตรงเดียวกันและมีทิศทางเดียวกัน คือจุดยอดอีกปลายหนึ่งมีมุมเชิงขั้วเท่ากันเมื่ออ้างอิงจุดยอดร่วม กำหนดให้ถึงเส้นเชื่อมที่มีหมายเลขน้อยกว่าก่อน กล่าวคือเส้นเชื่อมที่มีหมายเลขน้อยกว่ามีมุมเชิงขั้วน้อยกว่า

จงหาค่าสูงสุดของผลรวมพลังงานที่ได้รับหลังระบายสี ลบด้วยผลรวมค่าใช้จ่ายในการระบายสี

ข้อมูลนำเข้า

อ่านข้อมูลจากไฟล์ color.in

บรรทัดแรกมีจำนวนเต็มบวกสามจำนวน $n,m,p$ แทนจำนวนจุดยอด จำนวนเส้นเชื่อม และสัมประสิทธิ์พลังงาน ตามลำดับ

จากนั้น $m$ บรรทัด บรรทัดที่ $i$ มีจำนวนเต็มสามจำนวน $u_i,v_i,w_i$ แทนจุดยอดปลายทั้งสองและค่าใช้จ่ายของเส้นเชื่อมที่ $i$

จากนั้น $n$ บรรทัด บรรทัดที่ $i$ มีจำนวนเต็มสองจำนวน $x_i,y_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)$ หมุนทวนเข็มนาฬิการอบจุดยอด $4$ ไป $1$ เส้นเชื่อมจะถึง $(3,4)$ และได้รับพลังงาน $10\times1=10$; จาก $(2,3)$ หมุนทวนเข็มนาฬิการอบจุดยอด $3$ ไป $1$ เส้นเชื่อมจะถึง $(3,4)$ (สังเกตว่าตามข้อกำหนดในโจทย์ จะถึง $(3,4)$ ก่อน $(3,5)$) และได้รับพลังงาน $10\times1=10$; จาก $(3,5)$ หมุนทวนเข็มนาฬิการอบจุดยอด $3$ ไป $2$ เส้นเชื่อมจะถึง $(3,4)$ และได้รับพลังงาน $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$;
• สำหรับทุก $1\le i\le m$, $1\le u_i,v_i\le n$, $0\le w_i\le10^4$;
• สำหรับทุก $1\le i\le n$, $0\le x_i,y_i\le10^7$;
• กราฟที่กำหนดเป็นกราฟแคกตัส;
• ไม่มีจุดสองจุดใดมีพิกัดซ้ำกัน

คุณสมบัติพิเศษ A: รับประกันว่า $m=n-1$ กล่าวคือกราฟที่กำหนดเป็นต้นไม้

คุณสมบัติพิเศษ B: รับประกันว่าเส้นเชื่อมคู่ใดที่ไม่มีจุดยอดร่วมกันจะไม่ตัดกันบนระนาบ กล่าวคือกราฟที่กำหนดเป็นการฝังกราฟบนระนาบ

คุณสมบัติพิเศษ C: รับประกันว่าสำหรับทุก $1\le i\le m$, $w_i=0$

คุณสมบัติพิเศษ D: รับประกันว่าสำหรับทุก $1\le i\le m$, $w_i=1$ และ $p=1$