Problem

You are playing with J-kun using an Amidakuji (Ghost Leg lottery). The Amidakuji consists of $n$ vertical bars and $m$ horizontal bars. The vertical bars are numbered from $1$ to $n$ from left to right, and at the bottom end of vertical bar $i$, a positive integer $s_i$ is written.

Figure 3-1: Example of an Amidakuji ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

When tracing the path in order from the very top of vertical bar $i$, the integer written at the bottom end reached is the score when vertical bar $i$ is chosen. For example, in Figure 3-1, choosing vertical bar $1$ gives a score of $80$ points, and choosing vertical bar $2$ gives a score of $100$ points.

Figure 3-2: Example of how to trace paths

J-kun has decided to choose $k$ consecutive vertical bars from vertical bar $1$ to vertical bar $k$. The sum of the scores when choosing those $k$ vertical bars is J-kun's score. However, you may choose one horizontal bar in the Amidakuji and remove that horizontal bar from the Amidakuji (or you may choose not to remove any horizontal bar). If you remove one horizontal bar, J-kun's score will be the sum of the scores when choosing the $k$ consecutive vertical bars from vertical bar $1$ to vertical bar $k$ in the Amidakuji after the removal.

Given the shape of the Amidakuji and the number of vertical bars $k$ chosen by J-kun as input, write a program to find the minimum possible value of J-kun's score.

Input

• The $1$st line contains $4$ integers $n, m, h, k$ separated by spaces. $n$ ($2 \le n \le 1000$) represents the number of vertical bars, $m$ ($1 \le m \le 100000$) represents the number of horizontal bars, $h$ ($2 \le h \le 1000$) represents the length of the vertical bars, and $k$ ($1 \le k \le n$) represents the number of vertical bars chosen by J-kun.
• The following $n$ lines contain the scores written at the bottom ends of the vertical bars. The $(i + 1)$-th line ($1 \le i \le n$) contains a positive integer $s_i$. Furthermore, $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$ holds.
• The following $m$ lines contain the positions of the horizontal bars. The horizontal bars are numbered from $1$ to $m$. The $(i + n + 1)$-th line ($1 \le i \le m$) contains $2$ integers $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) separated by a space, representing the position of horizontal bar $i$: horizontal bar $i$ connects vertical bar $a_i$ and vertical bar $a_i + 1$, and its distance from the top end is $b_i$. No $2$ horizontal bars share an endpoint.

Of the test data, for $20\%$ of the score, J-kun's score is minimized when no horizontal bar is removed. Also, $30\%$ of the score satisfies $n \le 20, m \le 30, h \le 10$, and $60\%$ of the score satisfies $m \le 1000$.

Output

Output a single line containing only the minimum possible value of J-kun's score.

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

Sample Explanation

Sample 1 corresponds to Figure 3-1, and J-kun's score is minimized when you remove horizontal bar $4$ (the horizontal bar connecting vertical bar $1$ and vertical bar $2$ at a distance of $5$ from the top end). In Sample 2, J-kun's score is minimized when you do not remove any horizontal bar (see Figure 3-3).

Figure 3-3