Segments on the Line

You are a given a list of integers a_1, a_2, …, a_n and s of its segments [l_j; r_j] (where 1 ≤ l_j ≤ r_j ≤ n).

You need to select exactly m segments in such a way that the k-th order statistic of the multiset of a_i, where i is contained in at least one segment, is the smallest possible. If it's impossible to select a set of m segments in such a way that the multiset contains at least k elements, print -1.

The k-th order statistic of a multiset is the value of the k-th element after sorting the multiset in non-descending order.

Input

The first line contains four integers n, s, m and k (1 ≤ m ≤ s ≤ 1500, 1 ≤ k ≤ n ≤ 1500) — the size of the list, the number of segments, the number of segments to choose and the statistic number.

The second line contains n integers a_i (1 ≤ a_i ≤ 10^9) — the values of the numbers in the list.

Each of the next s lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) — the endpoints of the segments.

It is possible that some segments coincide.

Output

Print exactly one integer — the smallest possible k-th order statistic, or -1 if it's impossible to choose segments in a way that the multiset contains at least k elements.

Examples

Input

4 3 2 2 3 1 3 2 1 2 2 3 4 4

Output

2

Input

5 2 1 1 1 2 3 4 5 2 4 1 5

Output

1

Input

5 3 3 5 5 5 2 1 1 1 2 2 3 3 4

Output

-1

Note

In the first example, one possible solution is to choose the first and the third segment. Together they will cover three elements of the list (all, except for the third one). This way the 2-nd order statistic for the covered elements is 2.

inputFormat

Input

The first line contains four integers n, s, m and k (1 ≤ m ≤ s ≤ 1500, 1 ≤ k ≤ n ≤ 1500) — the size of the list, the number of segments, the number of segments to choose and the statistic number.

The second line contains n integers a_i (1 ≤ a_i ≤ 10^9) — the values of the numbers in the list.

Each of the next s lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) — the endpoints of the segments.

It is possible that some segments coincide.

outputFormat

Output

Print exactly one integer — the smallest possible k-th order statistic, or -1 if it's impossible to choose segments in a way that the multiset contains at least k elements.

Examples

Input

4 3 2 2 3 1 3 2 1 2 2 3 4 4

Output

2

Input

5 2 1 1 1 2 3 4 5 2 4 1 5

Output

1

Input

5 3 3 5 5 5 2 1 1 1 2 2 3 3 4

Output

-1

Note

In the first example, one possible solution is to choose the first and the third segment. Together they will cover three elements of the list (all, except for the third one). This way the 2-nd order statistic for the covered elements is 2.

样例

4 3 2 2
3 1 3 2
1 2
2 3
4 4

2

</p>