Умова задачі

Ви граєте з 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$, а відстань від верхнього кінця до перекладини $i$ дорівнює $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, і результат J-куна є мінімальним, коли ви видаляєте горизонтальну перекладину $4$ (перекладину, що з'єднує вертикальні палички $1$ та $2$ на відстані $5$ від верхнього кінця). У Прикладі 2 результат J-куна є мінімальним, коли ви не видаляєте жодної горизонтальної перекладини (див. Рисунок 3-3).

Рисунок 3-3