#P3104. Drying

    ID: 2105 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>贪心Northeastern Europe 2005Northern Subregion

Drying

题目描述: 在冬天,清洗和晾干衣物非常困难。但Jane是个聪明的女孩,她不惧怕这个枯燥的过程。Jane决定使用一个散热器来加快干燥速度。但散热器很小,一次只能放一件衣物。

Jane希望在尽可能短的时间内完成干燥。她请你编写一个程序,计算给定衣物的最小干燥时间。

Jane刚洗了nn件衣物。每件衣物在洗涤时吸收了aiai的水分。每分钟,每件衣物的水分会减少11(当然,只有在衣物还未完全干燥的情况下)。当水分降为零时,衣物干燥完成可以打包。

每分钟Jane可以选择一件衣物放在散热器上烘干。散热器非常热,可以使该衣物的水分每分钟减少kk(但不低于零——如果衣物的水分少于kk,则水分会降为零)。

任务是有效利用散热器,最小化总干燥时间。当所有衣物都干燥时,干燥过程结束。

输入: 第一行是一个整数n1n100,000n(1 ≤ n ≤ 100,000)。第二行是空格分隔的ai1ai109ai(1 ≤ ai ≤ 10^9)。第三行是k1k109k(1 ≤ k ≤ 10^9)

输出: 输出一个整数——干燥所有衣物所需的最少分钟数。