В последнее время в университет СортГУ стали поступать жалобы на то, что ученики не успевают делать домашнее задание по физике. Вот, например, прямо сейчас $n$ учеников должны $a_1, a_2, \dots, a_{n - 1}, a_n$ номеров (то есть $i$-й ученик должен $a_i$ задач).

Пришло время задавать очередную домашку. На этот раз преподаватели СортГУ решили поступить справедливо и задать каждому ученику такое количество примеров, чтобы в итоге все были должны одинаковое их количество, а суммарное количество задолженнных всеми ребятами номеров было максимальным. При этом в методическом пособии, из которого преподаватели берут задания, есть всего $m$ номеров, а один и тот же номер можно выдать только одному из учеников.

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

Входные данные

В первой строке записано число $n$ ($1 \le n \le 10^5$) - количество студентов, которым нужно раздать домашку.

Во второй строке записано $n$ чисел $a_1, a_2, \dots, a_n$, где $a_i$ - количество номеров, которое сейчас должен $i$-тый студент ($0 \le a_i \le 10^9$).

В третьей строке записано число $m$ ($0 \le m \le 10^9$) - количество номеров в методическом пособии.

Выходные данные

Если можно задать домашку так, как хочет СортГУ, то выведите, сколько номеров в сумме ученики будут должны в этом случае. Если домашку задать нельзя - выведете -1.

Подзадачи