Люк Скайуокер проходит изнурительные тренировки на всеми забытой планете Дагоба. Одним из самых сложных для него упражнений остаётся управление громоздкими объектами с помощью Силы. Люк должен одновременно удерживать в воздухе несколько камней. Это требует от него предельной концентрации и сосредоточенности, которые постоянно ускользают.

Люк выбрал определённый порядок камней и поднимает их один за другим строго в соответствии с этим порядком. Каждую секунду Люк поднимает в воздух очередной камень. Однако, если в эту секунду что-то отвлекло его внимание, он не только не поднимает камень, но ещё и роняет на землю часть поднятых ранее. Камни падают на землю в порядке, обратном тому, в котором они были подняты в воздух. Они падают до тех пор, пока суммарный вес упавших камней не превысит k килограмм или же пока в воздухе совсем не останется камней.

Упражнение будет считаться выполненным в тот момент, когда Люк поднимет в воздух все камни. Люк уже хорошо умеет смотреть в будущее и может предсказать все моменты, в которые он будет отвлекаться. Теперь он хочет понять, сколько времени уйдёт у него на то, чтобы закончить это упражнение и перейти к следующей тренировке.

В первой строке даны три целых числа n — общее количество камней, m — количество моментов, в которые Люк отвлечётся, и k (1 ≤ n, m ≤ 10⁵, 1 ≤ k ≤ 10⁹). В следующих n строках даны веса камней w_i в килограммах в том порядке, в котором Люк собирается поднимать их в воздух (1 ≤ w_i ≤ 10⁴). В следующих m строках даны моменты времени t_i, когда Люк отвлекается на разные события (1 ≤ t_i ≤ 10⁹, t_i < t_i+1).

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

В первые три секунды Люк поднимет камни весом 1, 2 и 3 килограмма. В четвёртую секунду он отвлечётся и уронит камни весом 2 и 3 килограмма. За следующие четыре секунды он поднимет все четыре лежащих на земле камня, и на этом его упражнение завершится.