Есептің шарты

Сіз 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-кун $1$ тік таяқшадан $k$ тік таяқшаға дейінгі қатар орналасқан $k$ таяқшаны таңдауды ұйғарды. Осы $k$ тік таяқшаны таңдаған кездегі ұпайлардың қосындысы J-кунның ұпайы болады. Алайда сіз амидакудзи ішіндегі бір көлденең таяқшаны таңдап, оны амидакудзиден өшіріп тастай аласыз (өшірмеуіңізге де болады). Егер сіз бір көлденең таяқшаны өшірсеңіз, өшіргеннен кейінгі амидакудзиде $1$ тік таяқшадан $k$ тік таяқшаға дейінгі қатар орналасқан $k$ тік таяқшаны таңдаған кездегі ұпайлардың қосындысы J-кунның ұпайы болады.

Кіріс ретінде амидакудзидің пішіні және J-кун таңдайтын тік таяқшалар саны $k$ берілгенде, 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$) бос орын арқылы бөлінген, $i$ көлденең таяқшасының орнын білдіретін $2$ бүтін сан $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) жазылған: $i$ көлденең таяқшасы $a_i$ тік таяқшасы мен $a_i + 1$ тік таяқшасын қосады және $i$ көлденең таяқшасының жоғарғы ұшынан қашықтығы $b_i$-ге тең. Ешқандай $2$ көлденең таяқшаның ортақ ұшы болмайды.

Тест деректерінің ішінде ұпайдың $20\%$ бөлігінде көлденең таяқшаны өшірмеген жағдайда J-кунның ұпайы ең аз болады. Сондай-ақ, ұпайдың $30\%$ бөлігі $n \le 20, m \le 30, h \le 10$ шартын, ал ұпайдың $60\%$ бөлігі $m \le 1000$ шартын қанағаттандырады.

Шығыс деректер

J-кунның ұпайының ең кіші мәні ғана бар $1$ жолды шығарыңыз.

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 сурет