Задача C. Плотники ≡

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:70  

Условие

Юные плотники Вася и Петя решили изготовить приставную лестницу. Для этого каждый из них взял по бруску длиной L см, и просверлил в нём по N дырок.

Затем плотники сложили бруски вместе, и заметили, что Васины дырки находятся на расстояниях a1, a2, …, aN см от начала бруска, а Петины — на расстояниях b1, b2, …, bN см от начала бруска.

Других брусков у Пети и Васи не было, и времени, чтобы сверлить дырки в других местах — тоже. Поэтому они решили просто отпилить от начала каждого бруска по куску так, чтобы как можно больше неотпиленных дырок совпало.

Требуется написать программу, которая определит, сколько сантиметров нужно отпилить от каждого из брусков.

Формат входного файла

Входной файл содержит целые числа N L, за которыми следует N целых чисел ai и N целых чисел bi.

Формат выходного файла

Выходной файл должен содержать целые числа A B — длины кусков, которые следует отпилить соответственно от первого и второго бруска, чтобы на оставшихся частях было как можно больше совпадающих дырок. Если существует несколько решений, вывести решение с наименьшим значением A, а если и таких решений несколько — решение с наименьшим значением B.

Ограничения

1 ≤ N ≤ 1000

2 ≤ L ≤ 1000

1 ≤ ai, bi < L, ai < ai + 1, bi < bi + 1

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1 3
2 1
 
1 0
2 
2 5
3 4 3 4
 
0 0
3 
3 10
3 5 6
1 8 9
 
0 3
0.036s 0.011s 15