CF1055E.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.

给定一个整数列表 $a_1, a_2, \ldots, a_n$，以及该列表的 $s$ 个区间 $[l_j; r_j]$（其中 $1 \le l_j \le r_j \le n$）。

你需要恰好选择 $m$ 个区间，使得所有被至少一个所选区间覆盖的下标 $i$ 对应的 $a_i$ 构成的多重集的第 $k$ 小值尽可能小。如果无法选出 $m$ 个区间，使得该多重集包含至少 $k$ 个元素，则输出 -1。

一个多重集的第 $k$ 小值（即第 $k$ 阶统计量）是指将该多重集按非降序排序后，第 $k$ 个位置上的元素值。

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.

第一行包含四个整数 $n$、$s$、$m$ 和 $k$（$1 \le m \le s \le 1500$，$1 \le k \le n \le 1500$）——分别表示列表的大小、线段总数、需选择的线段数量以及统计序号。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）——表示列表中各数字的值。

接下来的 $s$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）——表示第 $i$ 条线段的左右端点。

某些线段可能完全重合。

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.

输出一个整数——即可能的最小的第 $k$ 小元素；如果无法选择线段，使得多重集包含至少 $k$ 个元素，则输出 $-1$。

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$.

在第一个例子中，一种可能的解法是选择第一个和第三个区间。它们共同覆盖了列表中的三个元素（除第三个元素外的所有元素）。这样，被覆盖元素的第 $2$ 小值为 $2$。