Метро
Мер столиці Котоляндії врешті погодився побудувати в місті мережу метро. Тепер його очікує надзвичайно важливе завдання — зекономити якомога більше грошей на побудові цього метро.
Мережа метро буде складатись із певної кількості станцій, сполучених двосторонніми тунелями. Між будь-якою парою станцій повинен бути шлях по тунелях (можливо, через інші станції), при цьому кількість побудованих тунелів має бути мінімальною можливою. Зауважте, що за таких умов існує єдиний шлях між будь-якою парою станцій.Пасажири повинні будуть заплатити певну кількість грошей для того, щоб увійти в метро на певній станції. При цьому для різних станцій ця сума може бути різною. А саме: для деякої станції X вартість входу буде рівна (в гривнях) максимальній кількості тунелів, які пасажир має проїхати для того, щоб доїхати від станції X до будь-якої іншої станції Y.
Крім того, мер міста дуже прискіпливий до чисел. Відомо, що мер любить числа A[1], ..., A[N], а також ненавидить числа B[1], ..., B[M]. Мер не погодиться на побудову метро, якщо серед вартостей входу на станції будуть не всі його улюблені числа або буде хоча б одне, яке він ненавидить.
####ЗавданняНапишіть програму, яка за заданими числовими вподобаннями мера знаходитиме мінімальну кількість станцій, яку може містити метро, або визначатиме, що мережу із заданими вимогами побудувати неможливо.
Вхідні дані
Перший рядок вхідних даних містить два цілих числа N та M — кількість чисел, які мер любить та ненавидить відповідно. Другий рядок містить список із N цілих чисел, розділених пропусками, — список чисел, які мер любить. Третій рядок містить в аналогічному форматі список із M чисел, які мер ненавидить.
Вихідні дані
У єдиному рядку вихідних даних виведіть мінімальну кількість станцій, яку може містити метро. Якщо неможливо побудувати мережу зі заданими вимогами, виведіть одне число -1.
Оцінювання
Набір тестів складається з 2 блоків, для яких виконуються такі умови:
50 % балів:
1 ≤ N, M, A[i], B[i] ≤ 2000.50 % балів:
1 ≤ N, M, A[i], B[i] ≤ 100000.