Đề bài

Bạn đang chơi trò Amidakuji (thang ma) cùng với J-kun. Bảng Amidakuji gồm $n$ thanh dọc và $m$ thanh ngang. Các thanh dọc được đánh số từ $1$ đến $n$ theo thứ tự từ trái sang phải, và ở đầu dưới của thanh dọc $i$ có ghi một số nguyên dương $s_i$.

Hình 3-1: Ví dụ về Amidakuji ($n = 4, m = 5, s_1 = 20, s_2 = 80, s_3 = 100, s_4 = 50$)

Khi đi dọc theo đường dẫn bắt đầu từ đầu trên cùng của thanh dọc $i$, số nguyên ghi ở đầu dưới mà ta đi tới chính là số điểm đạt được khi chọn thanh dọc $i$. Ví dụ, trong Hình 3-1, nếu chọn thanh dọc $1$ thì điểm số là $80$ điểm, còn nếu chọn thanh dọc $2$ thì điểm số là $100$ điểm.

Hình 3-2: Ví dụ về cách đi theo đường dẫn

J-kun quyết định chọn $k$ thanh dọc liên tiếp từ thanh dọc $1$ đến thanh dọc $k$. Tổng số điểm khi chọn $k$ thanh dọc đó sẽ là điểm của J-kun. Tuy nhiên, bạn có thể chọn một thanh ngang trong bảng Amidakuji và xóa thanh ngang đó khỏi bảng Amidakuji (hoặc bạn cũng có thể không xóa thanh ngang nào). Nếu bạn xóa một thanh ngang, thì điểm của J-kun sẽ là tổng số điểm khi chọn $k$ thanh dọc liên tiếp từ thanh dọc $1$ đến thanh dọc $k$ trong bảng Amidakuji sau khi đã xóa.

Cho hình dạng của bảng Amidakuji và số lượng thanh dọc $k$ mà J-kun chọn, hãy viết chương trình tìm giá trị nhỏ nhất có thể của điểm số mà J-kun nhận được.

Dữ liệu vào

• Dòng thứ $1$ chứa $4$ số nguyên $n, m, h, k$ cách nhau bởi khoảng trắng. $n$ ($2 \le n \le 1000$) biểu thị số thanh dọc, $m$ ($1 \le m \le 100000$) biểu thị số thanh ngang, $h$ ($2 \le h \le 1000$) biểu thị chiều dài của các thanh dọc, và $k$ ($1 \le k \le n$) biểu thị số thanh dọc mà J-kun chọn.
• $n$ dòng tiếp theo ghi số điểm ở đầu dưới của các thanh dọc. Dòng thứ $(i + 1)$ ($1 \le i \le n$) chứa một số nguyên dương $s_i$. Ngoài ra, $s_1 + s_2 + \cdots + s_n \le 2000000000 = 2 \times 10^9$ được thỏa mãn.
• $m$ dòng tiếp theo ghi vị trí của các thanh ngang. Các thanh ngang được đánh số từ $1$ đến $m$. Dòng thứ $(i + n + 1)$ ($1 \le i \le m$) chứa $2$ số nguyên $a_i, b_i$ ($1 \le a_i \le n - 1, 1 \le b_i \le h - 1$) cách nhau bởi khoảng trắng biểu thị vị trí của thanh ngang $i$: thanh ngang $i$ nối thanh dọc $a_i$ với thanh dọc $a_i + 1$, và khoảng cách từ đầu trên cùng đến thanh ngang $i$ là $b_i$. Không có $2$ thanh ngang nào có chung đầu mút.

Trong dữ liệu chấm, $20\%$ số điểm có điểm của J-kun đạt nhỏ nhất khi không xóa thanh ngang nào. Ngoài ra, $30\%$ số điểm thỏa mãn $n \le 20, m \le 30, h \le 10$, và $60\%$ số điểm thỏa mãn $m \le 1000$.

Kết quả

In ra $1$ dòng duy nhất chỉ chứa giá trị nhỏ nhất của điểm số của J-kun.

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

Giải thích ví dụ

Ví dụ 1 tương ứng với Hình 3-1, và điểm của J-kun đạt nhỏ nhất khi bạn xóa thanh ngang $4$ (thanh ngang nối thanh dọc $1$ và thanh dọc $2$ ở vị trí cách đầu trên cùng một khoảng bằng $5$). Trong Ví dụ 2, điểm của J-kun đạt nhỏ nhất khi bạn không xóa thanh ngang nào (xem Hình 3-3).

Hình 3-3