← 返回题目列表

Codeforces · 350/A

A. 时间限制

中文机器翻译题面 查看原题

Valera 想要准备 Codesecrof 回合。他已经遇到了一个问题,并且想为其设置一个时间限制 (TL)。

Valera 写出了 n 个正确的解决方案。对于每个正确的解决方案,他知道其运行时间(以秒为单位)。 Valera 还写了 m 个错误的解决方案,并且对于每个错误的解决方案,他知道其运行时间(以秒为单位)。

假设 Valera 将在问题中设置 v 秒 TL。那么如果一个解决方案的运行时间最多为v秒,我们就可以说该解决方案通过了系统测试。我们还可以说,如果解决方案的运行时间(一秒)不等式 2a ≤ v 成立,则该解决方案在一些“额外”时间下通过了系统测试。

因此,Valera决定设置v秒TL,即满足以下条件:

1. v为正整数;
2.所有正确解均通过系统测试;
3. 至少有一个正确的解决方案通过了系统测试,并且需要一些“额外”的时间;
4.所有错误解法均未通过系统测试;
5. v 值在所有 TL 中最小,点 1、2、3、4 成立。

帮助 Valera 找到最合适的 TL,否则说明此类 TL 不存在。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 100)。第二行包含 n 个空格分隔的正整数 a1, a2, ..., an (1 ≤ ai ≤ 100) — n 个正确解中每个解的运行时间(以秒为单位)。第三行包含 m 个空格分隔的正整数 b1, b2, ..., bm (1 ≤ bi ≤ 100) — m 个错误解中每个解的运行时间(以秒为单位)。

输出

如果有有效的 TL 值,则打印它。否则,打印-1。

示例

输入 #1

3 6
4 5 2
8 9 6 10 7 11

输出 #1

5

输入 #2

3 1
3 4 5
6

输出 #2

-1