Background

Special for beginners, ^_^

Description

可以使用散热器烘干衣服。但散热器很小，所以它一次只能容纳一件衣服。

简有n 件衣服，每件衣服在洗涤过程中都带有ai 的水。在自然风干的情况下，每件衣服的含水量每分钟减少1（只有当物品还没有完全干燥时）。当含水量变为零时，布料变干并准备好包装。

在散热器上烘干时，衣服的含水量每分钟减少k （如果衣服含有少于k 的水，则衣服的含水量变为零）。请有效地使用散热器来最小化烘干的总时间。

Format

Input

输入：

第1行包含一个整数n （1≤n ≤10^5 ）；第2行包含ai（1≤ai ≤10^9 ，1≤i ≤n ）；第3行包含k （1≤k ≤10^9 ）

Output

单行输出烘干所有衣服所需的最少时间。

Samples

3
2 3 9
5

3

Limitation

1s, 1024KiB for each test case.