Woburn Challenge 2017-18 Round 2 - Senior Division
There's nothing like a bit of friendly competition, even when your life is on the line! Legolas and Gimli have taken to counting how many enemies they're each able to kill in each confrontation, in an effort to one-up one another.
During the battle of Helm's Deep, Legolas killed enemies, the of which had a strength level of . Meanwhile, Gimli killed enemies, the of which had a strength level of .
Though Gimli killed fewer enemies than Legolas did, he's not about to
admit defeat to the elf so easily. As such, he's gotten the idea to
introduce a new rule: "All enemies with strength levels smaller than
don't count" (for some positive integer no larger than ). Help
Gimli find any value of which would cause him to "win" (in other
words, such that Gimli killed strictly more enemies with strength levels
greater than or equal to than Legolas did). If no possible value of
would have this result, output -1
instead.
Subtasks
In test cases worth of the points, .
Input Specification
The first line of input consists of two space-separated integers,
and .
lines follow, the of which consists of a single integer
(for ).
lines follow, the of which consists of a single integer
(for ).
Output Specification
Output a single integer, any valid value of which would cause Gimli
to win, or -1
if there's no such value.
Sample Input 1
5 4
84
6
105
54
30
91
84
28
66
Sample Output 1
60
Sample Input 2
2 1
3
3
3
Sample Output 2
-1
Sample Explanation 2
In the first case, if , then Legolas's score will be (with his and killed enemies counting), while Gimli's score will be . Note that there exist other valid values of which would also be accepted.
In the second case, if , then both Legolas's score will be and Gimli's will be . If , then both scores will be . Either way, Gimli can't win.
Comments