410413: GYM104018 F Поиск сокровищ

F. Поиск сокровищограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Группа археологов обнаружила древний подземный город. Город состоит из $$$N$$$ пещер, расположенных по кругу, каждой пещере присвоен номер от $$$1$$$ до $$$N$$$.

Пещеры, между которыми расстояние по кругу равно в точности $$$K$$$, соединены двусторонними тоннелями.

На рисунке ниже приведен пример города с $$$N=8$$$ и $$$K=3$$$.

Археологи не просто так спустились в данный город: они точно знают, что в некоторых пещерах лежат сокровища. В группе $$$M$$$ археологов, и каждый из них рассказал остальным ровно об одной пещере с сокровищами.

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

Вам, как главному аналитику экспедиции, необходимо определить минимальное количество часов, за которое каждый археолог сможет добраться до одной из пещер с сокровищами:

• Все тоннели имеют одинаковую длину: археолог проходит тоннель за $$$1$$$ час;
• В одной и той же пещере и тоннеле могут находиться два и более археологов;
• В одной и той же пещере могут находиться два и более сокровищ;
• Каждый археолог может унести ровно одно сокровище — если в пещере $$$K$$$ сокровищ, то и добраться до них должны $$$K$$$ археологов.

Входные данные

В первой строке заданы целые числа $$$N$$$, $$$K$$$, $$$M$$$ ($$$3 \leq N \leq 10^6$$$; $$$1 \leq K < \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. Археолог из пещеры $$$1$$$ добирается до сокровища в пещере $$$7$$$ по маршруту $$$1 \rightarrow 4 \rightarrow 7$$$ за 2 часа.
2. Археолог из пещеры $$$4$$$ забирает сокровище из пещеры $$$4$$$, никуда не перемещаясь — всего 0 часов.
3. Археолог из пещеры $$$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$$$.

Один из примеров оптимального поиска сокровищ:

1. Археолог из пещеры $$$5$$$ добирается до сокровища в пещере $$$3$$$ по маршруту $$$5 \rightarrow 3$$$ за 1 час.
2. Археолог из пещеры $$$5$$$ добирается до сокровища в пещере $$$1$$$ по маршруту $$$5 \rightarrow 3 \rightarrow 1$$$ за 2 часа.
3. Археолог из пещеры $$$2$$$ добирается до сокровища в пещере $$$4$$$ по маршруту $$$2 \rightarrow 4$$$ за 1 час.
4. Археолог из пещеры $$$2$$$ добирается до сокровища в пещере $$$4$$$ по маршруту $$$2 \rightarrow 4$$$ за 1 час.
5. Археолог из пещеры $$$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$$$. Легко понять, что по системе тоннелей археолог никак не может добраться до сокровища.