Задача B. И о погоде
Задачу добавил: alef
Успешно сдано решений: 119
Ограничение по времени: 2 с на тест
Ограничение по памяти: 256 Мб
Для чемпионата надо подготовить дорожки для катания, засеяв их газоном. Но погода не балует устроителей: то дождь, то град, то похолодание...
В распоряжении устроителей имеется n сортов травы, которые мы будем обозначать числами от 1 до n. Для каждого сорта #iизвестна минимальная температура bi, при которой эта трава не погибнет.
Синоптики города S подготовили долгосрочный прогноз погоды. Для каждого из m ближайших дней они рассчитали минимальную температуру tj в день #j.
Вырастить хороший газон совсем не просто. Дорожка имеет длину d единиц, но в течение дня можно посадить траву только на одной единице длины. Устроители обратились к ландшафтному дизайнеру, сообщив ему прогноз погоды и характеристики сортов травы, и попросили его составить план посадки. По мнению устроителей этот план должен был выглядеть как последовательность из d номеров сортов травы p1, p2, ..., pd. В первый день нужно будет посадить траву сорта p1, во второй — траву сорта p2 и т.д.
Пропускать дни при посадке устроители не хотят, так что если в некоторый день высадка газона будет начата, то она будет непрерывно продолжаться в течение d дней.
Разумеется, вся трава должна быть высажена до дня m включительно, и вся высаженная трава не должна погибнуть до дня m включительно.
Ландшафтный дизайнер составил план посадки травы и передал его устроителям. Но оказалось, что при записи плана дизайнер поступил следующим образом: если в течение нескольких дней подряд нужно было сажать траву одного и того же сорта, он указывал номер этого сорта только один раз.
Устроители хотят понять, в какой день им следует начать реализовывать план дизайнера. Ваша задача — определить наиболее ранний день, подходящий для реализации плана.
В первой строке содержатся целые числа n, m, d (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 не переживет похолодания в последние два дня.