Сушіння#5363
Прати речі взимку — справа непроста, а сушити їх ще складніше. Але Джейн — кмітлива дівчина і не боїться домашньої рутини. Щоб пришвидшити сушіння, вона вирішила скористатися радіатором. Проте радіатор маленький і в кожний момент часу може сушити лише один предмет.
Джейн хоче висушити речі якнайшвидше. Вона просить вас написати програму, яка визначить мінімальний час, потрібний для сушіння всіх предметів.
Джейн щойно випрала предметів. Під час прання кожен предмет увібрав a_i одиниць води. Щохвилини кількість води у кожному предметі зменшується на (поки він ще не сухий). Щойно кількість води стає рівною , предмет вважається сухим і готовим до пакування.
Крім того, щохвилини Джейн може обрати один предмет і покласти його на радіатор. Радіатор досить гарячий, тому предмет на ньому втрачає одиниць води за хвилину (але не більше, ніж є всередині: якщо у предметі менше ніж одиниць води, він просто повністю висихає за цю хвилину).
Ваше завдання — визначити мінімальну кількість часу, необхідну для сушіння всіх предметів за оптимального використання радіатора. Сушіння вважається завершеним, коли всі предмети стають сухими.
Перший рядок містить одне ціле число n~(1 \le n \le 10^5) — кількість предметів.
Другий рядок містить цілих чисел a_i~(1 \le a_i \le 10^9), де a_i — кількість води у -му предметі після прання.
Третій рядок містить одне ціле число k~(1 \le k \le 10^9) — швидкість випаровування води з предмета, що лежить на радіаторі (в одиницях води за хвилину).
Виведіть одне число — мінімальну кількість хвилин, достатню для повного висушування всіх предметів.
Приклад 1
Приклад 2