ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2013, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Старый падаван

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Йода: Примени Силу. Да. Теперь камень. Почувствуй его. Сосредоточься!
Люк Скайуокер проходит изнурительные тренировки на всеми забытой планете Дагоба. Одним из самых сложных для него упражнений остаётся управление громоздкими объектами с помощью Силы. Люк должен одновременно удерживать в воздухе несколько камней. Это требует от него предельной концентрации и сосредоточенности, которые постоянно ускользают.
Люк выбрал определённый порядок камней и поднимает их один за другим строго в соответствии с этим порядком. Каждую секунду Люк поднимает в воздух очередной камень. Однако, если в эту секунду что-то отвлекло его внимание, он не только не поднимает камень, но ещё и роняет на землю часть поднятых ранее. Камни падают на землю в порядке, обратном тому, в котором они были подняты в воздух. Они падают до тех пор, пока суммарный вес упавших камней не превысит k килограмм или же пока в воздухе совсем не останется камней.
Упражнение будет считаться выполненным в тот момент, когда Люк поднимет в воздух все камни. Люк уже хорошо умеет смотреть в будущее и может предсказать все моменты, в которые он будет отвлекаться. Теперь он хочет понять, сколько времени уйдёт у него на то, чтобы закончить это упражнение и перейти к следующей тренировке.

Исходные данные

В первой строке даны три целых числа n — общее количество камней, m — количество моментов, в которые Люк отвлечётся, и k (1 ≤ n, m ≤ 105, 1 ≤ k ≤ 109). В следующих n строках даны веса камней wi в килограммах в том порядке, в котором Люк собирается поднимать их в воздух (1 ≤ wi ≤ 104). В следующих m строках даны моменты времени ti, когда Люк отвлекается на разные события (1 ≤ ti ≤ 109, ti < ti+1).

Результат

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

Пример

исходные данныерезультат
5 1 4
1
2
3
4
5
4
8

Замечания

В первые три секунды Люк поднимет камни весом 1, 2 и 3 килограмма. В четвёртую секунду он отвлечётся и уронит камни весом 2 и 3 килограмма. За следующие четыре секунды он поднимет все четыре лежащих на земле камня, и на этом его упражнение завершится.
Автор задачи: Денис Дублённых (подготовка — Егор Щелконогов)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1998. Старый падаван