2015-16 Woburn Challenge Finals - Senior Division

The monkeys have made a booming business out of selling their fur, and their newfound cash flow has been directed towards purchasing all kinds of dangerous weapons to be used against the cows. While the cows have sensed the general fact that the monkeys are about to strike, they are puzzled by how their enemies could be acquiring the necessary funds. Watching shipments of nondescript boxes move in and out of the monkeys' lair has put the entirety of Old MacDonald's farm on edge. To address the frustrating turn of events, Bo Vine has decided to send an elite group of $N$ $(1\le N\le {10}^6)$ cow spies on an important mission. This group of highly trained agents are to infiltrate the Sacred Tree, gathering intelligence about the monkeys' source of income and other vile plans! There's just one problem... he's noticed that the cows are all rather thirsty. Needing to ask for water during this assignment could very well blow their cover, so Bo Vine needs to ensure that they all get a drink before heading out! Fortunately, there are $M$ $(1\le M\le {10}^6)$ water troughs available in the barn.

The $i$-th cow is $C_i$ $(1\le C_i\le {10}^9)$ centimetres tall, while the $i$-th trough is $T_i$ $(1\le T_i\le {10}^9)$ centimetres high. Each cow is willing to drink from a trough if it's no taller than them, and no more than $K$ $(0\le K\le {10}^9)$ centimetres shorter than them – in other words, cow $i$ can drink from trough $j$ if $C_i-K\le T_j\le C_i$.

Each cow will need to drink from a trough of their choice for exactly 1 minute. The cows certainly like their privacy, so during each minute, each trough can be used by at most one cow. With not much time left until the start of their mission, Bo Vine needs your help to determine the minimum amount of time required for all of them to get a drink, if it's even possible!

In test cases worth $7/14$ of the points, $N\le 100$ and $M\le 100$.

Input Specification

The first line of input consists of three space-separated integers $N$, $M$, and $K$.
$N$ lines follow, with the $i$-th of these lines consisting of a single integer $C_i$ (for $i=1\dots N$).
$M$ lines follow, with the $i$-th of these lines consisting of a single integer $T_i$ (for $i=1\dots M$).

Output Specification

Output a single integer – the minimum number of minutes required for all of the cows to drink from a trough, or -1 if it's impossible.

Sample Input 1

4 4 5
13
24
10
13
20
8
14
22

Sample Output 1

3

Sample Explanation 1

The following is one optimal sequence of events:

• 1st minute: The 4th cow drinks from trough $2$ and the $2$nd cow drinks from trough $4$.
• 2nd minute: The 3rd cow drinks from trough $2$.
• 3rd minute: The 1st cow drinks from trough $2$.

Sample Input 2

2 1 0
1
1000000000
999999999

Sample Output 2

-1