Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Segments on the Line

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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.

Output

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.

Examples

Input

4 3 2 2

3 1 3 2

1 2

2 3

4 4

Output

2

Input

5 2 1 1

1 2 3 4 5

2 4

1 5

Output

1

Input

5 3 3 5

5 5 2 1 1

1 2

2 3

3 4

Output

-1

Note

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 08:53:10 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|