Условие задачи

Вы играете с 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