Метро

Мэр столицы Котоляндии наконец-то согласился на строительство метро в городе. Теперь перед ним стоит важная задача — максимально сократить расходы на это строительство.

Сеть метро будет включать несколько станций, соединенных двусторонними туннелями. Между любой парой станций должен существовать путь по туннелям (возможно, через другие станции), при этом количество построенных туннелей должно быть минимальным. Обратите внимание, что при таких условиях между любой парой станций будет существовать единственный путь.

Пассажиры должны будут заплатить определенную сумму за вход на станцию метро. Эта сумма может различаться для разных станций. Для станции X стоимость входа (в гривнах) будет равна максимальному количеству туннелей, которые пассажир должен преодолеть, чтобы добраться от станции X до любой другой станции Y.

Кроме того, мэр города очень придирчив к числам. Известно, что мэр любит числа A[1], ..., A[N], а ненавидит числа B[1], ..., B[M]. Мэр не одобрит строительство метро, если среди стоимостей входа на станции не окажутся все его любимые числа или будет хотя бы одно число, которое он ненавидит.

Задача

Напишите программу, которая по заданным числовым предпочтениям мэра определит минимальное количество станций, которое может содержать метро, или установит, что построить сеть с заданными требованиями невозможно.

Входные данные

Первая строка входных данных содержит два целых числа N и M — количество чисел, которые мэр любит и ненавидит соответственно. Вторая строка содержит список из N целых чисел, разделенных пробелами, — список чисел, которые мэр любит. Третья строка содержит аналогичный список из M чисел, которые мэр ненавидит.

Выходные данные

В единственной строке выходных данных выведите минимальное количество станций, которое может содержать метро. Если невозможно построить сеть с заданными требованиями, выведите одно число -1.

Примеры

Оценивание

Набор тестов состоит из 2 блоков, для которых выполняются следующие условия:

1. 50 % баллов: 1 ≤ N, M, A[i], B[i] ≤ 2000.

2. 50 % баллов: 1 ≤ N, M, A[i], B[i] ≤ 100000.