Ladder Game

Sanggeun is playing a ladder game. The ladder consists of $n$ vertical lines and $m$ horizontal bars. The vertical lines are numbered from $1$ to $n$, left to right, and a positive integer $s_i$ is written at the bottom of vertical line $i$.

Starting from the top of vertical line $i$ and following the ladder downward, you arrive at some cell at the bottom; the number written in that cell is the score you get for choosing vertical line $i$.

Sanggeun chooses the leftmost consecutive vertical lines, that is, lines $1$ through $k$. The sum of the scores obtained from the chosen lines is Sanggeun's score.

Sanggeun may erase at most one horizontal bar. If a bar is erased, each vertical line's destination cell is recomputed on the ladder that remains after the removal.

Given the shape of the ladder and the number of chosen vertical lines $k$, write a program that finds the smallest score Sanggeun can obtain.

The first line contains the number of vertical lines $n$ ($2 \le n \le 1000$), the number of horizontal bars $m$ ($1 \le m \le 100\,000$), the vertical length of the ladder $h$ ($2 \le h \le 1000$), and the number of chosen vertical lines $k$ ($1 \le k \le n$).

Each of the next $n$ lines contains the score $s_i$ written at the bottom of a vertical line, one per line. ($s_1 + s_2 + \cdots + s_n \le 2 \times 10^9$)

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ describing a bar's position. ($1 \le a_i \le n-1$, $1 \le b_i \le h-1$) Bar $i$ connects vertical lines $a_i$ and $a_i+1$, and its distance from the top of the ladder is $b_i$.

Print the smallest score Sanggeun can obtain on the first line.