Группа археологов обнаружила древний подземный город. Город состоит из $$$N$$$ пещер, расположенных по кругу, каждой пещере присвоен номер от $$$1$$$ до $$$N$$$.
Пещеры, между которыми расстояние по кругу равно в точности $$$K$$$, соединены двусторонними тоннелями.
На рисунке ниже приведен пример города с $$$N=8$$$ и $$$K=3$$$.
Археологи не просто так спустились в данный город: они точно знают, что в некоторых пещерах лежат сокровища. В группе $$$M$$$ археологов, и каждый из них рассказал остальным ровно об одной пещере с сокровищами.
Археологи хотят поскорее добраться до всех сокровищ — город древний, поэтому в любой момент своды могут начать обрушаться. В то же время каждый археолог не может унести более одного сокровища.
Вам, как главному аналитику экспедиции, необходимо определить минимальное количество часов, за которое каждый археолог сможет добраться до одной из пещер с сокровищами:
- Все тоннели имеют одинаковую длину: археолог проходит тоннель за $$$1$$$ час;
- В одной и той же пещере и тоннеле могут находиться два и более археологов;
- В одной и той же пещере могут находиться два и более сокровищ;
- Каждый археолог может унести ровно одно сокровище — если в пещере $$$K$$$ сокровищ, то и добраться до них должны $$$K$$$ археологов.
В первой строке заданы целые числа $$$N$$$, $$$K$$$, $$$M$$$ ($$$3 \leq N \leq 10^6$$$; $$$1 \leq K \lt \frac{N}{2}$$$; $$$1 \leq M \leq 1000$$$) — количество пещер в городе, расстояние между cоединенными тоннелем пещерами и количество археологов и сокровищ соответственно.
Во второй строке дано $$$M$$$ целых чисел $$$A_i$$$ ($$$1 \le A_i \le N$$$) — номера пещер, где изначально находятся археологи.
В третьей строке дано $$$M$$$ целых чисел $$$T_j$$$ ($$$1 \le T_j \le N$$$) — номера пещер, в которых находятся сокровища.
Выведите единственное целое число — минимальное число часов, за которое все $$$M$$$ сокровищ будут достигнуты и распределены по $$$M$$$ археологам.
Если археологи не могут добраться до всех сокровищ за любое количество времени, выведите $$$-1$$$.
8 3 3 1 4 6 4 5 7
3
5 2 5 5 2 2 2 5 3 4 1 4 3
2
6 2 1 1 2
-1
Первый тестовый пример
Карта города соответствует рисунку в условии задачи.
Археологи расположены в пещерах с номерами $$$1$$$, $$$4$$$ и $$$6$$$, а сокровища — в пещерах $$$4$$$, $$$5$$$ и $$$7$$$.
Один из примеров оптимального поиска сокровищ:
- Археолог из пещеры $$$1$$$ добирается до сокровища в пещере $$$7$$$ по маршруту $$$1 \rightarrow 4 \rightarrow 7$$$ за 2 часа.
- Археолог из пещеры $$$4$$$ забирает сокровище из пещеры $$$4$$$, никуда не перемещаясь — всего 0 часов.
- Археолог из пещеры $$$6$$$ добирается до сокровища в пещере $$$5$$$ по маршруту $$$6 \rightarrow 3 \rightarrow 8 \rightarrow 5$$$ за 3 часа.
В ответ пойдет максимальное из времён — 3 часа. Можно показать, что невозможно добраться до всех трёх сокровищ быстрее.
Второй тестовый пример
В городе $$$N = 5$$$ пещер, а тоннели расположены между пещерами на расстоянии $$$K = 2$$$:
- между $$$1$$$ и $$$3$$$;
- между $$$2$$$ и $$$4$$$;
- между $$$3$$$ и $$$5$$$;
- между $$$4$$$ и $$$1$$$;
- между $$$5$$$ и $$$2$$$.
Три археолога расположены в пещере $$$2$$$, а еще двое — в пещере $$$5$$$.
В пещерах $$$3$$$ и $$$4$$$ расположены по два сокровища; еще одно сокровище расположено в пещере $$$1$$$.
Один из примеров оптимального поиска сокровищ:
- Археолог из пещеры $$$5$$$ добирается до сокровища в пещере $$$3$$$ по маршруту $$$5 \rightarrow 3$$$ за 1 час.
- Археолог из пещеры $$$5$$$ добирается до сокровища в пещере $$$1$$$ по маршруту $$$5 \rightarrow 3 \rightarrow 1$$$ за 2 часа.
- Археолог из пещеры $$$2$$$ добирается до сокровища в пещере $$$4$$$ по маршруту $$$2 \rightarrow 4$$$ за 1 час.
- Археолог из пещеры $$$2$$$ добирается до сокровища в пещере $$$4$$$ по маршруту $$$2 \rightarrow 4$$$ за 1 час.
- Археолог из пещеры $$$2$$$ добирается до сокровища в пещере $$$3$$$ по маршруту $$$2 \rightarrow 5 \rightarrow 3$$$ за 2 часа.
В ответ пойдет максимальное из времён — 2 часа.
Третий тестовый пример
В городе $$$N = 6$$$ пещер, а тоннели расположены между пещерами на расстоянии $$$K = 2$$$:
- между $$$1$$$ и $$$3$$$;
- между $$$2$$$ и $$$4$$$;
- между $$$3$$$ и $$$5$$$;
- между $$$4$$$ и $$$6$$$;
- между $$$5$$$ и $$$1$$$;
- между $$$6$$$ и $$$2$$$.
Археолог расположен в пещере $$$1$$$, а сокровище — в пещере $$$2$$$. Легко понять, что по системе тоннелей археолог никак не может добраться до сокровища.
