โจทย์ปัญหา

คุณกำลังเล่นอามิดะคุจิ (เกมลากเส้นบันไดผี) กับ J-คุง อามิดะคุจิประกอบด้วยเส้นแนวตั้ง $n$ เส้น และเส้นแนวนอน $m$ เส้น เส้นแนวตั้งมีหมายเลขกำกับตั้งแต่ $1$ ถึง $n$ เรียงจากซ้ายไปขวา และที่ปลายด้านล่างของเส้นแนวตั้งที่ $i$ มีจำนวนเต็มบวก $s_i$ เขียนอยู่

รูปที่ 3-1: ตัวอย่างของอามิดะคุจิ ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

เมื่อไล่ตามเส้นทางลงมาจากด้านบนสุดของเส้นแนวตั้งที่ $i$ ตามลำดับ จำนวนเต็มที่เขียนอยู่ที่ปลายด้านล่างที่ไปถึงคือคะแนนที่ได้เมื่อเลือกเส้นแนวตั้งที่ $i$ ตัวอย่างเช่น ในรูปที่ 3-1 หากเลือกเส้นแนวตั้งที่ $1$ จะได้คะแนน $80$ คะแนน และหากเลือกเส้นแนวตั้งที่ $2$ จะได้คะแนน $100$ คะแนน

รูปที่ 3-2: ตัวอย่างวิธีการไล่ตามเส้นทาง

J-คุง ตัดสินใจเลือกเส้นแนวตั้ง $k$ เส้นที่อยู่ติดกันตั้งแต่เส้นแนวตั้งที่ $1$ ถึงเส้นแนวตั้งที่ $k$ ผลรวมของคะแนนเมื่อเลือกเส้นแนวตั้งทั้ง $k$ เส้นนั้นจะเป็นคะแนนของ J-คุง อย่างไรก็ตาม คุณสามารถเลือกเส้นแนวนอนหนึ่งเส้นในอามิดะคุจิและลบเส้นแนวนอนนั้นออกจากอามิดะคุจิได้ (หรือไม่ลบเลยก็ได้) หากคุณลบเส้นแนวนอนออกหนึ่งเส้น คะแนนของ J-คุง จะเท่ากับผลรวมของคะแนนเมื่อเลือกเส้นแนวตั้ง $k$ เส้นที่อยู่ติดกันตั้งแต่เส้นแนวตั้งที่ $1$ ถึงเส้นแนวตั้งที่ $k$ ในอามิดะคุจิหลังจากการลบแล้ว

เมื่อกำหนดรูปร่างของอามิดะคุจิและจำนวนเส้นแนวตั้ง $k$ ที่ J-คุง เลือกมาให้เป็นข้อมูลนำเข้า จงเขียนโปรแกรมเพื่อหาค่าต่ำสุดที่เป็นไปได้ของคะแนนของ J-คุง

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

• บรรทัดที่ $1$ มีจำนวนเต็ม $4$ จำนวน ได้แก่ $n, m, h, k$ คั่นด้วยช่องว่าง โดย $n$ ($2 \le n \le 1000$) แทนจำนวนเส้นแนวตั้ง, $m$ ($1 \le m \le 100000$) แทนจำนวนเส้นแนวนอน, $h$ ($2 \le h \le 1000$) แทนความยาวของเส้นแนวตั้ง และ $k$ ($1 \le k \le n$) แทนจำนวนเส้นแนวตั้งที่ J-คุง เลือก
• อีก $n$ บรรทัดถัดมาระบุคะแนนที่เขียนอยู่ที่ปลายด้านล่างของเส้นแนวตั้ง โดยบรรทัดที่ $(i + 1)$ ($1 \le i \le n$) มีจำนวนเต็มบวก $s_i$ นอกจากนี้ยังเป็นไปตามเงื่อนไข $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$
• อีก $m$ บรรทัดถัดมาระบุตำแหน่งของเส้นแนวนอน เส้นแนวนอนมีหมายเลขกำกับตั้งแต่ $1$ ถึง $m$ โดยบรรทัดที่ $(i + n + 1)$ ($1 \le i \le m$) มีจำนวนเต็ม $2$ จำนวน ได้แก่ $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) คั่นด้วยช่องว่าง แทนตำแหน่งของเส้นแนวนอนที่ $i$ ซึ่งหมายความว่าเส้นแนวนอนที่ $i$ เชื่อมระหว่างเส้นแนวตั้งที่ $a_i$ กับเส้นแนวตั้งที่ $a_i + 1$ และอยู่ห่างจากปลายด้านบนเป็นระยะทาง $b_i$ ทั้งนี้ ไม่มีเส้นแนวนอน $2$ เส้นใดที่ใช้จุดปลายร่วมกัน

ในข้อมูลทดสอบ สำหรับ $20\%$ ของคะแนน คะแนนของ J-คุง จะมีค่าน้อยที่สุดเมื่อไม่ลบเส้นแนวนอนใดๆ เลย นอกจากนี้ สำหรับ $30\%$ ของคะแนนจะเป็นไปตามเงื่อนไข $n \le 20, m \le 30, h \le 10$ และสำหรับ $60\%$ ของคะแนนจะเป็นไปตามเงื่อนไข $m \le 1000$

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

แสดงผล $1$ บรรทัดที่มีเฉพาะค่าต่ำสุดของคะแนนของ J-คุง

Sample 1

4 5 7 2
20
80
100
50
1 1
2 6
2 3
1 5
3 1

100

Sample 2

2 2 5 1
10
20
1 1
1 3

10

คำอธิบายตัวอย่าง

ตัวอย่างที่ 1 สอดคล้องกับรูปที่ 3-1 และเมื่อคุณลบเส้นแนวนอนที่ $4$ (เส้นแนวนอนที่เชื่อมเส้นแนวตั้งที่ $1$ กับเส้นแนวตั้งที่ $2$ ที่ระยะห่าง $5$ จากปลายด้านบน) คะแนนของ J-คุง จะมีค่าน้อยที่สุด ในตัวอย่างที่ 2 คะแนนของ J-คุง จะมีค่าน้อยที่สุดเมื่อคุณไม่ลบเส้นแนวนอนใดๆ เลย (ดูรูปที่ 3-3)

รูปที่ 3-3