사다리 게임

상근이는 사다리 게임을 하고 있다. 사다리는 $n$개의 세로줄과 $m$개의 가로 막대로 이루어져 있다. 세로줄에는 왼쪽에서 오른쪽으로 $1$번부터 $n$번까지 번호가 붙어 있고, 세로줄 $i$의 맨 아래에는 양의 정수 $s_i$가 적혀 있다.

세로줄 $i$의 맨 위에서 출발하여 사다리를 따라 내려가면 맨 아래의 어떤 칸에 도착하는데, 그 칸에 적혀 있는 점수가 세로줄 $i$를 선택했을 때 얻는 점수이다.

상근이는 왼쪽에서부터 연속된 세로줄, 즉 세로줄 $1$번부터 세로줄 $k$번까지를 선택한다. 선택한 세로줄들에서 얻는 점수의 합이 상근이의 점수가 된다.

상근이는 가로 막대를 최대 한 개까지 지울 수 있다. 막대를 하나 지운 경우에는, 그 막대를 지운 뒤의 사다리를 기준으로 각 세로줄의 도착 칸을 다시 계산한다.

사다리의 모양과 선택한 세로줄의 수 $k$가 주어질 때, 상근이가 얻을 수 있는 가장 작은 점수를 구하는 프로그램을 작성하시오.

첫째 줄에 세로줄의 개수 $n$ ($2 \le n \le 1000$), 가로 막대의 개수 $m$ ($1 \le m \le 100,000$), 사다리의 세로 길이 $h$ ($2 \le h \le 1000$), 상근이가 선택한 세로줄의 수 $k$ ($1 \le k \le n$)가 주어진다.

다음 $n$개의 줄에는 각 세로줄의 맨 아래에 적힌 점수 $s_i$가 한 줄에 하나씩 주어진다. ($s_1 + s_2 + \cdots + s_n \le 2 \times 10^9$)

다음 $m$개의 줄에는 각 막대의 위치를 나타내는 두 정수 $a_i$와 $b_i$가 주어진다. ($1 \le a_i \le n-1$, $1 \le b_i \le h-1$) $i$번째 막대는 세로줄 $a_i$과 세로줄 $a_i+1$을 연결하며, 사다리의 맨 위에서부터의 거리는 $b_i$이다.

첫째 줄에 상근이가 얻을 수 있는 최소 점수를 출력한다.