CF1055E Segments on the Line

给定一个整数序列 $a_1, a_2, \ldots, a_n$，以及该序列的 $s$ 个区间 $[l_j, r_j]$（其中 $1 \le l_j \le r_j \le n$）。 你需要恰好选择 $m$ 个区间，使得被至少一个区间覆盖的 $a_i$ 组成的多重集合的第 $k$ 小值尽可能小。如果无法选择 $m$ 个区间使得多重集合中元素数量不少于 $k$，输出 $-1$。 多重集合的第 $k$ 小值指的是将多重集合中的元素按非降序排列后，第 $k$ 个元素的值。

第一行包含四个整数 $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$），表示每个区间的左右端点。 可能存在一些区间完全相同。

输出一个整数，表示所能取得的最小第 $k$ 小值。如果无法选择 $m$ 个区间使得多重集合中元素数量不少于 $k$，输出 $-1$。

在第一个样例中，一种可行的方案是选择第一个和第三个区间。它们一共覆盖了序列中的三个元素（除了第三个元素以外的所有元素）。这样，被覆盖元素的第 $2$ 小值为 $2$。  由 ChatGPT 4.1 翻译