晾衣服
题号:NC235254
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 64 M,其他语言128 M
64bit IO Format: %lld

题目描述

在冬天洗衣服特别是烘干衣服非常困难。但小红是一个非常聪明的女孩。她不怕这个无聊的过程,决定使用散热器来加快干燥速度。但是散热器很小,所以一次只能容纳一件衣服。
小红刚洗完n件衣服。第i件衣服在清洗过程中吸入了a_i单位的水。每分钟,每件衣服中含有的水就会减少1单位(只有当衣服还没有完全干燥时)。当所含的水量变为0时,衣服就算干燥了。
每分钟,小红都可以选择一件衣服在散热器上烘干。散热器非常热,所以在散热器上的衣服的水量每分钟会减小k单位(但不会小于0,如果这件衣服含有少于k单位的水,则水量将边为0)。
当所有衣服都干燥时,烘干过程结束。小红希望在尽可能短的时间内进行烘干。她要求你编写一个程序,用于计算给定衣服的最短烘干时间。

输入描述:

第一行输入一个整数n,
第二行输入n个整数a_1,a_2,...,a_n
第三行输入一个整数k

输出描述:

输出一个整数,表示烘干所有衣服所需要的最小分钟数。
示例1

输入

复制
3
3 2 9
5

输出

复制
3
示例2

输入

复制
3
3 2 6
5

输出

复制
2