문제

당신은 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