Задача C. Удобный момент
Задачу добавил: alef
Успешно сдано решений: 272
Будущий программист Кеша каждый день сталкивается с новыми задачами.
Кеша получил n простых заданий и одно сложное (для него). Для каждого из простых заданий Кеша может точно сказать, сколько времени ai он потратит на его выполнение, а вот как подступиться к сложному заданию, Кеша не знает.
В начале стажировки Кешу познакомили с опытным программистом Потапом и сказали, что при возникновении вопросов Кеше следует обращаться к Потапу. Именно так Кеша и собирается сделать, однако есть два важных обстоятельства.
Во-первых, Кеша считает, что обращаться к Потапу сразу же неправильно, и нужно самому потратить некоторое время, не меньшее b, и хотя бы немного разобраться в сложном задании. Конечно, Кеша может повозиться со сложным заданием и больше времени, но считает это непродуктивным.
Во-вторых, Потап не любит отвлекаться. Кеша знает, что у Потапа есть m заданий, и для каждого задания #j известно, сколько времени cj Потап на него потратит. Обратиться к Потапу Кеша может только в тот момент, когда Потап завершил работу над очередным заданием. Когда Потап завершит работу над заданием #m, то, если Кеша не обратится к нему сразу же, Потап отправится домой.
И Кеша, и Потап начнут работу в одно и то же время и будут выполнять задания по порядку. Единственным исключением является сложное задание Кеши, которое он может начать выполнять по завершении выполнения любого очередного задания или даже самым первым. Если Кеша начал выполнять сложное задание, он будет заниматься им в течение как минимум b единиц времени и до тех пор, пока ему не предоставится возможность задать вопрос Потапу.
Кеша хотел бы, чтобы время, в течение которого он будет заниматься сложным заданием, как можно меньше отличалось от b. Ваша задача — определить, каким по счёту Кеше следует начать делать сложное задание.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество простых заданий, полученных Кешей.
Во второй строке содержится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 104, i = 1, 2, ..., n), ai — время, которое понадобится Кеше на выполнение задания #i.
В третьей строке содержится целое число b (1 ≤ b ≤ 105) — минимальное время, в течение которого Кеша считает необходимым заниматься сложным заданием.
В четвёртой строке содержится целое число m (1 ≤ m ≤ 105) — количество заданий, полученных Потапом.
В пятой строке содержится m целых чисел c1, c2, ..., cm (1 ≤ cj ≤ 104, j = 1, 2, ..., m), cj — время, которое понадобится Потапу на выполнение задания #j.
Выведите целое число k — номер сложного задания в последовательности заданий Кеши, удовлетворяющий требованию задачи.
Если существует несколько вариантов ответа, выведите минимальное значение k.
Если Кеша не успеет обратиться к Потапу, выведите в качестве ответа 0.
Подзадача 1 (до 30 баллов)
1 ≤ n, m ≤ 1000.
Баллы начисляются за каждый пройденный тест.
Подзадача 2 (до 70 баллов)
1 ≤ n, m ≤ 100000.
Баллы начисляются за каждый пройденный тест.
По запросу сообщается результат проверки на каждом тесте.
5
10 8 5 11 9
20
7
12 15 14 7 11 3 10
3
5
8 13 7 11 10
80
4
12 20 8 14
0
Поясним приведённые примеры.
В первом примере Кеше следует выполнять сложное задание третьим по счёту. Тогда он будет готов задать вопрос Потапу спустя 38 единиц времени: за 18 единиц времени он выполнит первые два (простых) задания, а затем в течение 20 единиц времени будет размышлять над сложным.
Что касается Потапа, спустя 41 единицу времени он завершит выполнение третьего из своих заданий, так что Кеша, подождав 3 единицы времени, сможет задать вопрос Потапу.
Несложно видеть (выполнив непосредственный подсчёт), что это лучший результат.
Например, если Кеша решит выполнять сложное задание четвёртым, то будет готов задать вопрос Потапу спустя 43 единицы времени, но спустя 41 единицу времени Потап возьмётся за новое задание, которое завершит лишь на 48 единице времени. А это значит, что ждать Кеше придётся 5 единиц времени.
Аналогично можно выполнить проверку остальных вариантов.
Во втором примере даже если Кеша займётся с самого начала именно сложным заданием, он не успеет задать вопрос Потапу. Потап выполнит все свои четыре задания за 54 единицы времени, после чего отправится домой, а Кеша будет обдумывать сложное задание в течение 80 единиц времени.