Problem G. Дракон и рыцарь
Input file name: standard input
Output file name: standard output
Time limit: 1 s
Memory limit: 256 MB

Странствующий рыцарь как-то вызвал на бой живущего рядом дракона. Долгой была битва, и победил в ней рыцарь... И только он занёс меч, чтобы последним ударом срубить дракону голову, как вдруг услышал:

- Пожалей меня, добрый рыцарь! Я с тобой расплачусь!

- А как?

- Я тебе отдам четыре…нет, три любых драгоценных камня из моей сокровищницы!

Рыцарь посмотрел на свой заплатанный плащ, на прохудившиеся сапоги — и согласился. Но в последний момент в драконе взыграла природная жадность, и он сказал:

- Но суммарная стоимость камней не должна быть слишком большой! Я ценю свою жизнь в M золотых! Так что суммарная стоимость камней не должна превысить M!

Задумался рыцарь…Считать — не мечом махать! Ведь каждый камень имеет свою цену, а подобрать камни так, чтобы их суммарная стоимость не превысила оговоренной суммы, но была максимальной, непросто. Помогите ему!

Input

Первая строка содержит величину N — количество камней в сокровищнице дракона (3 ≤ N ≤ 5000, в 80 % тестов эта величина не превосходит 1000, а в 50 % тестов — 500). В следующей строке записаны N целых положительных чисел, не превосходящих 10000 — цена каждого камня. Наконец, в последней строке записано значение M (3 ≤ M ≤ 10000). Тесты подобраны так, что решение существует.

Output

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

Example


standard input standard output
5
25 27 31 14 28
70
70

Note

В примере необходимо взять первый, третий и четвёртый камни.