Language issues#209

Language issues

1 second
256 megabytes
Medium

Your dream has come true — you got into university! But there is one problem: you don't know what language your classes will be in. That's why you signed up for language courses. Today, your teacher came up with a very interesting exercise, but she can't choose the pairs for it, and if you don't help her, she will spend the whole class time trying out all possible combinations.

You are given students who attend the courses with you. The -th student's language proficiency level is a_i. There are also volunteers who can help you. The -th volunteer's language proficiency level is b_i. The pair should consist of a student and a volunteer, and a pair can be formed if the sum of their language proficiency levels is at least . Each person can be in at most one pair. You can invite the first volunteers from the list. Find the minimum value of such that all students have a pair, or output "-1" if it's impossible to form pairs regardless of the chosen .

Input

The first line contains three integers (1\leq n\leq 10^5), (1 \le m \le 10^5), and (1 \le x \le 10^9) — the number of students, the number of volunteers, and the minimum sum of language proficiency levels in a pair, respectively.

The second line contains integers a_i (0 \le a_i \le 10^9) — the language proficiency levels of the students.

The third line contains integers b_i (0 \le b_i \le 10^9) — the language proficiency levels of the volunteers.

Output

Output one integer — the answer to the problem.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Example 5

Loading
Loading

Example 6

Loading
Loading

Note

Explanation for the first example:

If we choose j=1, we won't be able to form a second pair.

If we choose j=2, there will be two possible pairs: \{(1,9),(4,1)\} and \{(1,1),(4,9)\}. The sum of language proficiency levels in the first pair is 1+4=5, which is less than x=6, so it doesn't fit. The sum of language proficiency levels in the second pair is 1+1=2, which is less than x=6, so it doesn't fit either. Since there is no way to form pairs, we can't choose j=2.

If we choose j=3, one of the possible pairings is \{(1,9),(4,2)\}. The sum of language proficiency levels in each pair is greater than or equal to , so the answer is .

Scoring

Solutions that correctly solve the task for n\leq 100 will be awarded at least 20 points.