ประเทศ IOI จะปรับปรุงโครงข่ายคมนาคมทั้งหมด ประเทศ IOI แทนด้วยระนาบพิกัด $xy$ ซึ่งมีเมือง $N$ เมือง เมืองที่ $i$ ($1\le i\le N$) แทนด้วยจุด $(X_i,Y_i)$ การปรับปรุงโครงข่ายคมนาคมดำเนินการดังนี้

• สร้างสนามบินนานาชาติในบางเมืองจาก $N$ เมือง ต้องสร้างสนามบินนานาชาติอย่างน้อยหนึ่งแห่ง การสร้างแต่ละแห่งมีค่าใช้จ่ายคงที่
• สร้างถนนบางสายเชื่อมระหว่างเมือง ถนนเป็นส่วนของเส้นตรงที่เชื่อมจุดแทนเมืองสองจุดโดยตรง และขนานกับแกน $x$ หรือแกน $y$ ค่าใช้จ่ายในการสร้างถนนแต่ละสายเท่ากับความยาวของถนน

ต้องเป็นไปตามเงื่อนไขต่อไปนี้

• ประเทศ IOI มีพื้นที่ $M$ แห่งที่ไม่สามารถสร้างถนนได้ เช่น เนื่องจากสภาพพื้นดินไม่ดี แต่ละพื้นที่แทนด้วยสี่เหลี่ยมผืนผ้า พื้นที่ที่ $j$ ($1\le j\le M$) มีมุมล่างซ้าย $(P_j,Q_j)$ และมุมบนขวา $(R_j,S_j)$ (กล่าวคือ $P_j<R_j$ และ $Q_j<S_j$) ถนนทุกสายต้องไม่มีส่วนร่วมกับพื้นที่ทั้ง $M$ แห่ง พื้นที่รวมขอบเขตด้วย จึงห้ามมีถนนที่มีส่วนร่วมกับเส้นรอบรูปของสี่เหลี่ยมผืนผ้าเช่นกัน
• จากเมืองใด ๆ ใน $N$ เมือง ต้องสามารถเดินทางตามถนนไปยังเมืองอื่นต่อ ๆ กันจนถึงเมืองที่มีสนามบินนานาชาติได้

มีบริษัทก่อสร้าง $C$ บริษัทเป็นผู้สมัครรับงานนี้ บริษัทที่ $k$ ($1\le k\le C$) มีค่าใช้จ่ายในการสร้างสนามบินนานาชาติแต่ละแห่งเท่ากับ $B_k$ และสร้างได้มากที่สุด $H_k$ แห่ง (ค่าใช้จ่ายในการสร้างถนนไม่ขึ้นอยู่กับบริษัท และไม่มีข้อจำกัดจำนวนหรือความยาวถนน) สำหรับแต่ละบริษัท เราต้องการหาค่าใช้จ่ายรวมที่น้อยที่สุดในการปรับปรุงโครงข่ายคมนาคมให้เป็นไปตามเงื่อนไขข้างต้น

บางบริษัทอาจไม่สามารถทำให้เป็นไปตามเงื่อนไขได้ เพราะสร้างสนามบินได้น้อยเกินไป ในกรณีนั้น ให้รายงานว่าไม่สามารถทำตามเงื่อนไขได้แทนการรายงานค่าใช้จ่ายรวม

งาน

จงเขียนโปรแกรมที่รับจำนวนเมือง $N$ และพิกัดของเมือง จำนวนพื้นที่ห้ามสร้างถนน $M$ และพิกัดแทนแต่ละพื้นที่ จำนวนบริษัทผู้สมัคร $C$ และข้อมูลของแต่ละบริษัท แล้วหาค่าใช้จ่ายรวมที่น้อยที่สุดสำหรับแต่ละบริษัทในการปรับปรุงโครงข่ายคมนาคมให้เป็นไปตามเงื่อนไขในโจทย์

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

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกมีจำนวนเต็มสามจำนวน $N,M,C$ คั่นด้วยช่องว่าง แทนจำนวนเมือง จำนวนพื้นที่ห้ามสร้างถนน และจำนวนบริษัทผู้สมัครตามลำดับ
• บรรทัดที่ $i$ ($1\le i\le N$) จาก $N$ บรรทัดถัดไป มีจำนวนเต็มสองจำนวน $X_i,Y_i$ คั่นด้วยช่องว่าง แทนพิกัด $(X_i,Y_i)$ ของเมืองที่ $i$
• บรรทัดที่ $j$ ($1\le j\le M$) จาก $M$ บรรทัดถัดไป มีจำนวนเต็มสี่จำนวน $P_j,Q_j,R_j,S_j$ คั่นด้วยช่องว่าง แทนพิกัดมุมล่างซ้าย $(P_j,Q_j)$ และมุมบนขวา $(R_j,S_j)$ ของสี่เหลี่ยมผืนผ้าที่เป็นพื้นที่ห้ามสร้างถนนแห่งที่ $j$
• บรรทัดที่ $k$ ($1\le k\le C$) จาก $C$ บรรทัดถัดไป มีจำนวนเต็มสองจำนวน $B_k,H_k$ คั่นด้วยช่องว่าง แทนว่าบริษัทผู้สมัครที่ $k$ ใช้ค่าใช้จ่าย $B_k$ ต่อสนามบินนานาชาติหนึ่งแห่ง และสร้างได้มากที่สุด $H_k$ แห่ง

ข้อมูลส่งออก

เขียนข้อมูล $C$ บรรทัดไปยังข้อมูลส่งออกมาตรฐาน บรรทัดที่ $k$ ($1\le k\le C$) มีจำนวนเต็มหนึ่งจำนวน แทนค่าใช้จ่ายรวมที่น้อยที่สุดหากบริษัทผู้สมัครที่ $k$ ดำเนินโครงการนี้ แต่หากบริษัทนั้นไม่สามารถดำเนินโครงการให้เป็นไปตามเงื่อนไขได้ ให้ส่งออกจำนวนเต็ม $-1$ แทน

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $1\le N\le 200\,000$
• $1\le M\le 200\,000$
• $1\le C\le 500\,000$
• $0\le X_i\le 1\,000\,000\,000$ ($1\le i\le N$)
• $0\le Y_i\le 1\,000\,000\,000$ ($1\le i\le N$)
• ไม่มีเมืองสองเมืองหรือมากกว่านั้นอยู่ที่พิกัดเดียวกัน
• $0\le P_j<R_j\le 1\,000\,000\,000$ ($1\le j\le M$)
• $0\le Q_j<S_j\le 1\,000\,000\,000$ ($1\le j\le M$)
• ไม่มีพื้นที่ใดมีเมืองอยู่ภายในหรือบนขอบเขตของสี่เหลี่ยมผืนผ้า
• $1\le B_k\le 1\,000\,000\,000$ ($1\le k\le C$)
• $1\le H_k\le N$ ($1\le k\le C$)

งานย่อย

งานย่อย 1 [10 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $M\le 100$
• $C\le 100$

งานย่อย 2 [30 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $C\le 100$

งานย่อย 3 [30 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $M\le 100$

งานย่อย 4 [30 คะแนน]

ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

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

4 2 3
1 1
10 1
1 10
10 10
4 0 8 9
1 4 9 8
7 4
10 3
1 1

ข้อมูลส่งออก 1

28
38
-1

หมายเหตุ

ข้อมูลตัวอย่างนี้แสดงได้ดังรูปต่อไปนี้ สี่เหลี่ยมผืนผ้าเส้นหนาแสดงพื้นที่ที่ห้ามสร้างถนน

สามารถสร้างถนนเชื่อมเมือง $2$ กับเมือง $4$ และเมือง $3$ กับเมือง $4$ ได้ แต่ไม่สามารถสร้างถนนระหว่างเมือง $1$ กับเมือง $2$ ได้ เพราะจะตัดกับพื้นที่ห้ามสร้างถนน เช่นเดียวกัน ไม่สามารถสร้างถนนระหว่างเมือง $1$ กับเมือง $3$ ได้ (โปรดทราบว่าถนนต้องไม่มีส่วนร่วมกับเส้นรอบรูปของสี่เหลี่ยมผืนผ้าด้วย)

บริษัทแรกสร้างสนามบินนานาชาติได้มากที่สุด 4 แห่ง โดยมีค่าใช้จ่ายแห่งละ 7 ในกรณีนี้ วิธีที่ดีที่สุดคือสร้างสนามบินในทุกเมืองโดยไม่สร้างถนนเลย ค่าใช้จ่ายรวมเท่ากับ $7\times4=28$

บริษัทที่สองสร้างสนามบินนานาชาติได้มากที่สุด 3 แห่ง โดยมีค่าใช้จ่ายแห่งละ 10 ในกรณีนี้ ตัวอย่างวิธีที่ดีที่สุดคือสร้างถนนยาว 9 เชื่อมเมือง $2$ กับเมือง $4$ และเมือง $3$ กับเมือง $4$ แล้วสร้างสนามบินในเมือง $1$ และเมือง $2$ ค่าใช้จ่ายรวมเท่ากับ $10\times2+9+9=38$

บริษัทที่สามสร้างสนามบินนานาชาติได้มากที่สุด 1 แห่ง โดยมีค่าใช้จ่ายแห่งละ 1 แต่เนื่องจากเมือง $1$ ไม่สามารถมีถนนเชื่อมกับเมืองอื่นใดได้ จึงต้องสร้างสนามบินอย่างน้อย 2 แห่งเพื่อให้เป็นไปตามเงื่อนไข บริษัทนี้จึงดำเนินโครงการไม่ได้ และส่งออก $-1$