#2456. 烘干衣服

烘干衣服

Description

可以使用散热器烘干衣服。但散热器很小,所以它一次只能容纳一件衣服。简有nn 件衣服,每件衣服在洗涤过程中都带有aia_i 的水。在自然风干的情况下,每件衣服的含水量每分钟减少11(只有当物品还没有完全干燥时)。当含水量变为零时,布料变干并准备好包装。在散热器上烘干时,衣服的含水量每分钟减少kk (如果衣服含有少于kk 的水,则衣服的含水量变为零)。请有效地使用散热器来最小化烘干的总时间。

Input

11行包含一个整数n1n105n (1≤n ≤10^5 );第2行包含ai1ai1091ina_i(1≤a_i ≤10^9 ,1≤i ≤n );第3行包含k1k109k (1≤k ≤10^9 )

Output

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

Samples

3 
2 3 9
5
3
2 3 6
5
3
2

来源

POJ3104