Метро#7666
Мер столиці Котоляндії врешті погодився побудувати в місті мережу метро. Тепер його очікує надзвичайно важливе завдання — зекономити якомога більше грошей на побудові цього метро.
Мережа метро буде складатися із певної кількості станцій, сполучених двосторонніми тунелями. Між будь-якою парою станцій повинен бути шлях по тунелях (можливо, через інші станції), при цьому кількість побудованих тунелів має бути мінімальною можливою. Зауважте, що за таких умов існує єдиний шлях між будь-якою парою станцій.
Пасажири повинні будуть заплатити певну кількість грошей для того, щоб увійти в метро на певній станції. При цьому для різних станцій ця сума може бути різною. А саме: для деякої станції вартість входу буде рівна (в гривнях) максимальній кількості тунелів, які пасажир має проїхати для того, щоб доїхати від станції до будь-якої іншої станції .
Крім того, мер міста дуже прискіпливий до чисел. Відомо, що мер любить числа A_1, \ldots, A_N, а також ненавидить числа B_1, \ldots, B_M. Мер не погодиться на побудову метро, якщо серед вартостей входу на станції будуть не всі його улюблені числа або буде хоча б одне, яке він ненавидить.
Напишіть програму, яка за заданими числовими вподобаннями мера знаходить мінімальну кількість станцій, яку може містити метро, або визначає, що мережу із заданими вимогами побудувати неможливо.
Перший рядок вхідних даних містить два цілих числа та — кількість чисел, які мер любить та ненавидить відповідно.
Другий рядок містить список із цілих чисел, розділених пропусками — список чисел, які мер любить.
Третій рядок містить в аналогічному форматі список із чисел, які мер ненавидить.
У єдиному рядку вихідних даних виведіть мінімальну кількість станцій, яку може містити метро. Якщо неможливо побудувати мережу зі заданими вимогами, виведіть одне число .
Приклад 1
Приклад 2
Набір тестів складається з двох блоків, для яких виконуються такі умови:
балів: 1 \leq N, M, A_i, B_i \leq 2000
балів: 1 \leq N, M, A_i, B_i \leq 100000