Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Мало је познато да је за одржавање другог дана СИО потребно активирати машину коју Комисија држи у једном подруму, која ће заменити задатке за први дан са задацима за други. Та машина има прилично компликован систем за активацију, који чине трака дужине \(L\) поља, од којих на \(N\) постоје прекидачи.

На траци се налази \(N\) кликера (сви су на различитим пољима), и за активацију је неопходно да се у истом тренутку на сваком прекидачу налази по кликер. Чланови Комисије ово обично постижу тако што одједном гурну све кликере, тако да се крећу лево или десно (различити кликери се могу кретати у различитим смеровима) константном брзином од једног поља у секунди. Кликери се могу сударати са крајевима траке или међусобно, у ком случају се одбијају и настављају истом брзином у супротном смеру (погледајте објашњење примера за пример одбијања).

Пошто члан Комисије који је требало да активира машину нема времена да смисли како ће то урадити, јер гледа утакмицу између Манчестер Вилиџа и Фејк Мадрида, на вама је да одредите како треба усмерити кликере. Пошто до другог дана СИО нема превише времена, треба да пронађете решење које ће активирати машину у што краћем времену.

Опис улаза

У првом реду стандардног улаза налазе се два цела броја \(L\) и \(N\) – број поља на траци и број кликера. У другом реду налази се \(N\) бројева \(A_1, A_2, \dots, A_n\), који представљају тренутне позиције свих кликера. У трећем и последњем реду се такође налази \(N\) бројева \(B_1, B_2, \dots, B_n\), који представљају позиције прекидача.

Позиције су индексиране од 1, тј. првом пољу траке одговара \(A_i = 1\), а последњем \(A_i = L\).

Опис излаза

У првом и једином реду стандардног излаза исписати један цео број \(T\) – најмање време (у секундама) за које је могуће довести све кликере на прекидаче. Уколико је то немогуће, исписати -1.

Пример 1

Улаз

4 2
2 4
1 4

Излаз

1

Пример 2

Улаз

8 4
1 3 6 7
1 3 5 8

Излаз

2

Објашњење примера

У првом примеру, ако се први кликер креће лево, а друга десно, после једне секунде ће се прва померити једно поље лево, а друга ударити у крај траке и вратити се на своју почетну позицију (требаће јој пола секунде да дође до зида и пола секунде назад, тако да јој позиција остаје иста).

У другом примеру, правци у којима је потребно да се кликери крећу да би се довели на прекидаче за две секунде су редом: десно, лево, десно и лево. Прве две куглице ће се сударити и вратити на почетне позиције. Друге две ће се такође међусобно одбити.

Ограничења

Постоји \(5\) подзадатака, у којима додатно важи:

Напомена