← 返回题目列表

Codeforces · 1055/E

E. 线上的段

中文机器翻译题面 查看原题

你有一个给定的整数列表 $$$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$$$ 阶统计量尽可能最小,其中 $$$i$$$ 至少包含在一个段中。如果不可能以多重集包含至少 $$$k$$$ 元素的方式选择一组 $$$m$$$ 段,则打印 -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$$$ 阶统计量,如果无法以多重集至少包含 $$$k$$$ 元素的方式选择段,则打印 -1。

示例

输入 #1

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

输出 #1

2

输入 #2

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

输出 #2

1

输入 #3

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

输出 #3

-1

注意

在第一个示例中,一个可能的解决方案是选择第一和第三段。它们将一起涵盖列表中的三个元素(除第三个元素外的所有元素)。这样,所覆盖元素的 $$$2$$$-nd 顺序统计量为 $$$2$$$。