Segments on the Line

题意翻译

给定 $n$ 个点，以及 $s$ 条线段，选择 $m$ 条线段，使得至少被一个线段覆盖的点的权值从小到大排序后，排名为 $k$ 的点的权值最小，若不可能产生 $k$ 个覆盖的点则输出 $-1$。 **【输入】** 第一行，四个数 $n,s,m,k$。 第二行，$n$ 个数表示点的坐标。 接下来 $s$ 行，每行两个数表示每条线段的左右端点。

题目描述

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.

输入输出样例

输入样例 #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

说明

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