Рудольф подготовил набор из \(n\) задач со сложностями \(a_1 < a_2 < a_3 < \dots < a_n\). Он не совсем доволен балансом, поэтому хочет добавить не больше одной задачи, чтобы его исправить.
Для этого Рудольф придумал \(m\) моделей задач и \(k\) функций. Сложность \(i\)-й модели равна \(d_i\), а сложность \(j\)-й функции равна \(f_j\). Чтобы составить задачу, он выбирает значения \(i\) и \(j\) (\(1 \le i \le m\), \(1 \le j \le k\)) и, совмещая \(i\)-ю модель с \(j\)-й функцией, получает новую задачу сложности \(d_i + f_j\) (в массив \(a\) добавляется новый элемент).
Чтобы определить дисбаланс набора, Рудольф сортирует сложности задач по возрастанию и находит самое большое значение \(a_i - a_{i - 1}\) (\(i > 1\)).
Какого минимального значения дисбаланса может добиться Рудольф, добавив не больше одной задачи, составленной по описанным правилам?
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальный дисбаланс, которого сможет добиться Рудольф.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5 5 5
5 10 15 20 26
11 14 16 13 8
16 4 5 3 1
7 6 5
1 4 7 10 18 21 22
2 3 5 7 4 2
6 8 9 3 2
7 6 5
1 4 7 10 18 21 22
2 3 5 7 4 2
6 8 13 3 2
5 6 3
2 10 13 20 25
11 6 10 16 14 5
6 17 15
4 2 2
11 12 14 15
19 14
10 6
8 4 2
3 10 16 18 21 22 29 30
9 13 16 15
4 2
2 4 7
4 21
4 15 14 5
20 1 15 1 12 5 11
|
5
4
5
8
2
7
11
|