Bạn đang chơi trò rút thăm bằng sơ đồ thang cùng bạn J. Sơ đồ 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. Ở đầu dưới của thanh dọc \(i\) có ghi số nguyên dương \(s_i\).

Nếu chọn thanh dọc \(i\), bạn bắt đầu từ đầu trên của thanh đó rồi đi xuống. Mỗi khi gặp một thanh ngang, bạn đi sang thanh dọc kề bên qua thanh ngang đó rồi tiếp tục đi xuống. Số ghi ở đầu dưới mà bạn đến được là điểm nhận được khi chọn thanh dọc \(i\).

Trong sơ đồ trên, chọn thanh dọc \(1\) được \(80\) điểm, còn chọn thanh dọc \(2\) được \(100\) điểm. Hai đường đi này được tô đậm trong hình dưới đây.

J quyết định chọn \(k\) thanh dọc liên tiếp từ thanh \(1\) đến thanh \(k\). Điểm của J bằng tổng điểm nhận được từ \(k\) lựa chọn này. Bạn được phép xóa nhiều nhất một thanh ngang khỏi sơ đồ; cũng có thể không xóa thanh nào. Nếu bạn xóa một thanh ngang, điểm của J được tính trên sơ đồ sau khi xóa.

Yêu cầu

Cho sơ đồ thang và số thanh dọc \(k\) mà J chọn. Tìm điểm nhỏ nhất mà J có thể nhận được khi bạn xóa nhiều nhất một thanh ngang.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng thứ nhất chứa bốn số nguyên \(n,m,h,k\) cách nhau bởi dấu cách. Trong đó \(h\) là chiều dài mỗi thanh dọc.
• \(n\) dòng tiếp theo lần lượt chứa \(s_1,s_2,\ldots,s_n\), mỗi dòng một số nguyên.
• \(m\) dòng tiếp theo mô tả các thanh ngang, được đánh số từ \(1\) đến \(m\) theo thứ tự nhập. Dòng thứ \(i\) trong số này chứa hai số nguyên \(a_i,b_i\) cách nhau bởi dấu cách: thanh ngang \(i\) nối thanh dọc \(a_i\) với thanh dọc \(a_i+1\) tại vị trí cách đầu trên của các thanh dọc một khoảng \(b_i\).

Không có hai thanh ngang nào chung đầu mút.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: điểm nhỏ nhất mà J có thể nhận được.

Ràng buộc

• \(2\le n\le 1000\).
• \(1\le m\le 100\,000\).
• \(2\le h\le 1000\).
• \(1\le k\le n\).
• \(s_i\) là số nguyên dương và \(s_1+s_2+\cdots+s_n\le 2\times 10^9\).
• \(1\le a_i\le n-1\) và \(1\le b_i\le h-1\).
• Không có hai thanh ngang nào chung đầu mút.
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(64\) MB.

Chấm điểm

Bài có \(10\) bộ dữ liệu, mỗi bộ \(2\) điểm, tổng cộng \(20\) điểm.

• \(20\%\) số điểm (\(4\) điểm) ứng với các bộ dữ liệu mà không xóa thanh ngang nào cũng đạt điểm nhỏ nhất cho J.
• \(30\%\) số điểm (\(6\) điểm) ứng với các bộ dữ liệu thỏa mãn \(n\le 20\), \(m\le 30\), \(h\le 10\).
• \(60\%\) số điểm (\(12\) điểm) ứng với các bộ dữ liệu thỏa mãn \(m\le 1000\).

Các điều kiện trên có thể cùng đúng trên một bộ dữ liệu.

Ví dụ

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

100

Ví dụ này tương ứng với sơ đồ đầu tiên. Điểm của J nhỏ nhất khi xóa thanh ngang \(4\), là thanh nối thanh dọc \(1\) và thanh dọc \(2\) tại vị trí cách đầu trên một khoảng \(5\).

2 2 5 1
10
20
1 1
1 3

10

Trong ví dụ này, không xóa thanh ngang nào sẽ cho điểm nhỏ nhất của J.

Hình bên trái dưới đây minh họa cách xóa thanh ngang trong ví dụ 1; hình bên phải minh họa ví dụ 2.