你有一个给定的整数列表 $$$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$$$。