Drying#5363
Washing clothes in winter is no easy task, and drying them is even more challenging. But Jane is a clever girl and isn't afraid of routine chores. To speed up the drying process, she decided to use a radiator. However, the radiator is small and can dry only one item at a time.
Jane wants to dry the laundry as quickly as possible. She's asking you to write a program that determines the minimum amount of time needed to dry the entire set of clothes.
Jane has just washed items. During the wash, each item absorbed a_i units of water. Every minute, the amount of water in each item decreases by (as long as the item is not yet dry). Once the amount of water reaches , the item is considered dry and can be packed.
Additionally, each minute, Jane can choose one item and place it on the radiator. The radiator is hot enough that an item placed on it loses units of water per minute (but no more than the amount of water it contains: if an item has less than units of water, it simply dries completely in that minute).
Your task is to determine the minimum amount of time needed to dry all the clothes with optimal use of the radiator. Drying is considered complete when all items are fully dry.
The first line contains one integer n~(1 \le n \le 10^5) — the number of items.
The second line contains integers a_i~(1 \le a_i \le 10^9), where a_i is the amount of water in the -th item after washing.
The third line contains one integer k~(1 \le k \le 10^9) — the evaporation rate of water from an item placed on the radiator (in units of water per minute).
Print one integer — the minimum number of minutes required to completely dry all items.
Example 1
Example 2