시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 6 6 75.000%

문제

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

세로줄 i의 상단부터 순서대로 길을 따라가게 되고, 하단에 적혀있는 정수가 그 막대기 i를 선택할 때 얻는 정수이다. 예를 들어, 위의 그림에서 세로줄 1을 선택하면 80점을 얻게 되고, 2를 선택하면 100점을 얻게 된다.

상근이는 세로줄 1부터 세로줄 k까지 연속된 세로줄 k개를 선택한다. 그리고, 선택한 세로줄의 점수의 합계가 상근이의 점수가 된다. 상근이는 막대를 최대 한 개 지울 수 있다. 만약, 막대를 하나 제거한다면, 제거하고 난 이후에 사다리를 타야 한다.

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

입력

첫째 줄에 세로줄의 개수 n(2 ≤ n ≤ 1000), 막대의 개수 m(1 ≤ m ≤ 100000), 막대의 길이 h(2 ≤ h ≤ 1000), 상근이가 선택한 세로줄의 수 k(1 ≤ k ≤ n)가 주어진다.

다음 n개 줄에는 세로 막대의 하단에 적혀있는 점수 si가 주어진다. (s1 + s2 + ... + sn ≤ 2*109)

다음 m개 줄에는 막대 i의 위치를 나타내는 ai와 bi가 주어진다. (1 ≤ ai ≤ n-1, 1 ≤ bi ≤ h-1) 막대 i는 세로줄 ai와 ai+1을 연결하고, 상단으로부터의 거리가 bi이다.

출력

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

예제 입력

4 5 7 2
20
80
100
50
1 1
2 6
2 3
1 5
3 1

예제 출력

100

힌트

출처

Olympiad > 일본정보올림피아드 > JOI 2009 3번