Реєстрація
Обмеження: 2 сек., 256 МіБ
Успішно прибувши до місця призначення запорожцем-лімузином, наші герої вирушили на реєстрацію. Реєстрація команд проводиться в нескінченно довгому коридорі, який, для спрощення, уважатимемо віссю OX з додатними координатами.
Усього є n організаторів, які здійснюють процес реєстрації, та m команд, які потрібно зареєструвати на змагання. i-ий організатор стоїть у координаті ai, а i-а команда — в координаті bi. За одну секунду кожен з організаторів може переміститися на одну одиницю відстані вліво або вправо. Команда вважається зареєстрованою на змагання, якщо її відвідав хоча б один організатор. Процес реєстрації відбувається миттєво. Декільком організаторам дозволено перебувати одночасно в одному місці.
Обчисліть мінімальний час, за який можна зареєструвати всі команди на змагання.
Вхідні дані
У першому рядку задано два цілі числа n та m — кількості організаторів та команд відповідно.
У другому рядку задано n чисел ai — координати i-го організатора.
У третьому рядку задано m чисел bi — координати i-ої команди.
Вихідні дані
В одному рядку виведіть ціле число — мінімальний час, за який організатори зможуть зареєструвати всі команди.
Обмеження
1≤n,m≤5⋅104,
1≤ai,bi≤109,
для 12 тестів виконуються обмеження:
n=2,
1≤m≤103.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 2 3 4 1 1 7 3 | 3 |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 2 4 3 8 1 4 2 12 | 4 |
Примітки
У першому прикладі 1-й організатор за 3 секунди переміститься в координату 7 та зареєструє другу команду, а 2-й організатор на 0-й секунді зареєструє першу команду, а на 2-й секунді — третю. Отже, потрібно 3 секунди, щоб зареєструвати всі команди.
У другому прикладі 1-му організатору вигідно спочатку зареєструвати другу команду, а потім третю та першу, на це йому знадобиться 4 секунди. Водночас 2-й організатор зареєструє четверту команду за 4 секунди. Отже, потрібно 4 секунди, щоб зареєструвати всі команди.