A12118 | Segments on the Line

You are a given a list of integers $a_1, a_2, \ldots, a_n$ and $s$ of its segments $[l_j; r_j]$ (where $1 \le l_j \le r_j \le 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.

The first line contains four integers $n$ , $s$ , $m$ and $k$ ( $1 \le m \le s \le 1500$ , $1 \le k \le n \le 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 \le a_i \le 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 \le l_i \le r_i \le n$ ) — the endpoints of the segments.

It is possible that some segments coincide.

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.