Кирилл — маленький зеленый монстрик, который очень любит читать книги. Именно поэтому он поступил в низший университет литературы. Домашнее задание Кирилла было очень простым — ему задали прочитать $$$n$$$ книг, пронумерованных целыми числами от $$$1$$$ до $$$n$$$. Известно, что в $$$i$$$-й книге было $$$a_i$$$ страниц. Кирилл должен читать книги именно в том порядке, в котором ему их выдали. Иными словами, он должен сначала прочитать книгу с номером $$$1$$$, затем прочитать книгу с номером $$$2$$$, и так далее.
На это задание Кириллу было отведено ровно $$$m$$$ дней, пронумерованных целыми числами от $$$1$$$ до $$$m$$$. При этом в $$$i$$$-й день он может прочитать только $$$b_i$$$ страниц. Таким образом, в каждый из этих $$$m$$$ дней (сначала в день с номером $$$1$$$, затем в день с номером $$$2$$$, и так далее) Кирилл будет выполнять задание и читать книги. За каждый из $$$m$$$ дней Кирилл может прочитать некоторое (возможно, нулевое) количество книг, соблюдая порядок их прочтения. Разумеется, Кирилл не будет читать одну и ту же книгу дважды.
Кирилл, конечно, умный монстрик, но у него есть одна серьезная проблема — если в какой-то день он не дочитает книгу до конца, то за ночь он все забудет, и на следующий день придется читать ее с самого начала. Также у Кирилла есть $$$k$$$ банок вишневого сока. Если в $$$i$$$-й день мальчик выпивает банку вишневого сока, то он может прочитать дополнительно $$$x$$$ страниц. При этом врач запретил ему пить в день более одной банки, так как это негативно скажется на его здоровье.
Как вы уже поняли, Кирилл поступил в университет литературы, а не программирования, поэтому вам придется посчитать, какое максимальное количество книг он сможет прочитать.
Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$) — количество книг.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — количество страниц в $$$i$$$-й книге.
Третья строка содержит одно целое число $$$m$$$ ($$$1 \le m \le 100\,000$$$) — количество отведенных дней для того, чтобы прочитать эти книги.
Четвертая строка содержит $$$m$$$ целых чисел $$$b_1, \ldots, b_m$$$ ($$$1 \le b_i \le 10^9$$$) — количество страниц, которые Кирилл может прочитать в $$$i$$$-й день.
Пятая строка содержит два целых числа $$$k$$$ и $$$x$$$ ($$$0 \le k \le 10$$$, $$$0 \le x \le 10^9$$$) — количество банок вишневого сока, а также количество страниц, которые Кирилл сможет дополнительно прочитать, выпив банку сока.
Выведите единственное целое число — максимальное количество книг, которые сможет прочитать Кирилл.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Тесты из условия | полная | |
| 1 | 10 | $$$n, m \le 8$$$ | первая ошибка | |
| 2 | 10 | $$$n, m \le 20$$$ | 1 | первая ошибка |
| 3 | 5 | $$$n \le 20$$$, $$$m \le 27$$$ | 1, 2 | первая ошибка |
| 4 | 15 | $$$k = 0$$$ | первая ошибка | |
| 5 | 20 | $$$a_i = 1$$$ для всех $$$1 \le i \le n$$$ | первая ошибка | |
| 6 | 20 | $$$k = 1$$$, $$$n, m \le 1\,000$$$ | первая ошибка | |
| 7 | 20 | нет | 1 – 6 | первая ошибка |
55 2 2 3 445 1 1 50 0
3
52 2 2 2 231 1 52 1
4
Рассмотрим первый пример. У Кирилла нет банок с соком, что сильно упрощает задачу. В первый день он может прочитать пять страниц, чего хватает ровно на одну книгу. В следующий день Кирилл читает одну страницу, но не дочитывает книгу до конца, из-за чего на следующий день придется читать ее сначала. В третий день происходит то же самое. В четвертый день Кирилл снова может прочитать ровно пять страниц, чего хватит на прочтение второй и третьей книг.
Рассмотрим второй пример. Если бы у Кирилла не было банок с соком, то он смог бы прочитать всего две книги. Но он может выпить сок в первый и второй дни. Тогда его способности по прочтению страниц будут следующими: $$$[2, 2, 5]$$$. Этого хватит на прочтение четырех книг.
| Name |
|---|