Задача №115409. Лучший бегун
Все бегуны будут тренироваться в течение \(T\) секунд. Тренировка бегуна выглядит так:
Пусть в текущий момент бегун находится в начале дорожки \(i\). Он пробегает до конца текущей дорожки за \(a_i\) секунд. Далее он может либо моментально переместиться в начало текущей дорожки, либо в начало \((i - 1)\)-й дорожки (если \(i > 1\)), либо в начало \((i + 1)\)-й дорожки (если \(i < n\)). После этого он продолжает бег с дорожки, на которую переместился. Как только длительность тренировки достигает \(T\) секунд, он завершает тренировку.
Назовём лучшим того бегуна, который пробежит наибольшее количество полных дорожек за время тренировки (таких бегунов может быть несколько). Определите, сколько дорожек пробежит лучший бегун.
Первая строка содержит три целых числа \(n\), \(m\) и \(T\) (\(1 \le m \le n \le 300\,000\), \(1 \le T \le 10^9\)) — количество дорожек, количество бегунов и длительность тренировки.
Вторая строка содержит \(n\) целых чисел \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\(1 \le a_i \le 10^9\)) — длины дорожек.
Третья строка содержит \(m\) целых чисел \(b_1\), \(b_2\), \(\ldots\), \(b_m\) (\(1 \le b_1 < b_2 < \ldots < b_m \le n\)) — номера дорожек, с которых начинают бегуны.
Выведите единственное число — максимальное количество полных дорожек, которое может пробежать за время тренировки один из бегунов.
В первом примере больше всех дорожек может пробежать бегун, начинающий на дорожке \(4\): он должен пробежать дорожку \(4\), после переместиться на дорожку \(5\) и пробежать её \(3\) раза.
Во втором примере бегун, начинающий на дорожке \(2\), может пробежать вторую дорожку \(2\) раза.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(T\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 23 | \(n \le 1000\) | – | – | 0 | |
| 2 | 10 | – | – | – | – | \(a_i \le a_{i + 1}\) для всех \(1 \le i \lt n\) |
| 3 | 16 | – | \(T \le 20\) | – | 0 | |
| 4 | 19 | – | – | \(a_i \le 20\) | 0 | |
| 5 | 11 | – | – | – | – | \(m = n\) |
| 6 | 21 | – | – | – | 0 – 5 | |
5 3 10 4 5 2 7 1 1 2 4
4
4 2 11 4 5 7 10 2 3
2