Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 





Задача B. И о погоде

Задачу добавил: alef

Успешно сдано решений: 115

Ограничение по времени: 2 с на тест

Ограничение по памяти: 256 Мб

Для чемпионата надо подготовить дорожки для катания, засеяв их газоном. Но погода не балует устроителей: то дождь, то град, то похолодание... 

В распоряжении устроителей имеется n сортов травы, которые мы будем обозначать числами от 1 до n. Для каждого сорта #iизвестна минимальная температура bi, при которой эта трава не погибнет. 

Синоптики города S подготовили долгосрочный прогноз погоды. Для каждого из m ближайших дней они рассчитали минимальную температуру tj в день #j.

Вырастить хороший газон совсем не просто. Дорожка имеет длину d единиц, но в течение дня можно посадить траву только на одной единице длины. Устроители обратились к ландшафтному дизайнеру, сообщив ему прогноз погоды и характеристики сортов травы, и попросили его составить план посадки. По мнению устроителей этот план должен был выглядеть как последовательность из d номеров сортов травы p1, p2, ..., pd. В первый день нужно будет посадить траву сорта p1, во второй — траву сорта p2 и т.д. 

Пропускать дни при посадке устроители не хотят, так что если в некоторый день высадка газона будет начата, то она будет непрерывно продолжаться в течение d дней.

Разумеется, вся трава должна быть высажена до дня m включительно, и вся высаженная трава не должна погибнуть до дня m включительно.

Ландшафтный дизайнер составил план посадки травы и передал его устроителям. Но оказалось, что при записи плана дизайнер поступил следующим образом: если в течение нескольких дней подряд нужно было сажать траву одного и того же сорта, он указывал номер этого сорта только один раз.

Устроители хотят понять, в какой день им следует начать реализовывать план дизайнера. Ваша задача — определить наиболее ранний день, подходящий для реализации плана.

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

В первой строке содержатся целые числа nmd (1 ≤ n ≤ 105,  1 ≤ d ≤ 105,  d ≤ m ≤ 105) — количество сортов травы, количество дней, для которых сделан прогноз погоды, длина дорожки.

Во второй строке содержатся целые числа bi (i = 1, 2, ..., n,  0 ≤ b1 < b2 < ... < bn ≤ 106), где bi — минимальная температура, приемлемая для сорта травы #i.

В третьей строке содержатся целые числа tj (0 ≤ tj ≤ 106,  j = 1, 2, ..., m), где tj — минимальная температура в день #j согласно прогнозу синоптиков.

В четвертой строке содержится целое число q (1 ≤ q ≤ d) — длина плана, который представил ландшафтный дизайнер.

В пятой строке содержится q целых чисел через пробел s1, s2, ..., sq (1 ≤ sk ≤ n,  k = 1, 2, ..., q) — номера сортов травы в порядке их высадки.

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

Выведите минимально возможный номер дня, в который следует начать посадку согласно предложенному плану.

Если реализовать план невозможно, выведите  - 1.

Система оценки

Подзадача 1 (до 20 баллов)

1 ≤ n ≤ 100,  1 ≤ d ≤ 100,  d ≤ m ≤ 100.

Баллы начисляются за каждый пройденный тест.

Подзадача 2 (до 80 баллов)

Все величины из условия могут принимать любые допустимые значения.

Баллы начисляются в случае прохождения всей группы тестов.

По запросу сообщается первый непройденный тест.

Примеры

входные данные
8 15 7
3 5 8 11 14 17 21 22
0 4 2 7 5 9 8 13 15 18 20 17 23 19 20
4
3 5 6 4
выходные данные
6
входные данные
3 8 5
2 6 9
4 5 8 4 5 9 6 8
3
2 3 1
выходные данные
-1

Примечание

Поясним приведённые примеры.

В первом случае «укороченный» план 3 5 6 4 ландшафтного дизайнера может быть «развёрнут» следующим образом: 3 3 3 5 6 6 4. Такой план можно начать реализовывать уже в день #6.

Во втором случае план реализовать не удастся: трава сорта #3 не переживет похолодания в последние два дня.

Сдать задачу

Задать вопрос жюри по этой задаче