# Barrels

##### Output: stdout

A lot of bugs from Bugland have invaded a wine cellar trough a magic portal. The wine cellar consists of $N$ rooms, each full with barrels of wine, and the $i^{th}$ room being infested with $V_i$ bugs.

The owners of the wine cellar have at their disposal $N$ insecticides of two types: $K$ sprays named AntiBug, which can remove $P$ bugs a day, and $N-K$ sprays named ZeroBugs, which can remove $Q$ bugs a day. Every day, a spray is used in every room.

Given those details, what is the minimum number of days in which the barrels of wine are saved by eliminating all the bugs?

# Input data

The first line will contain two numbers, $N$ and $K$, on the second one $P$ and $Q$, and on the third $N$ numbers, the $i^{th}$ representing the number of bugs $V_i$ from the $i^{th}$ room.

# Output data

The first line will contain the minimum number of days necessary to eliminate all the bugs.

# Constraints and clarifications

• $K \leq N \leq 2\cdot 10^5$
• $P, Q \leq 10^9$
• $V_i \leq 10^9\ \forall\ 1 \leq i \leq N$
• For tests worth 40 points: $K \leq N \leq 10^4$, $P, Q \leq 100$ and $V_i \leq 10^4$
• A spray can be used in a single room each day, and two sprays cannot be used in the same room because using different types of sprays simultaneously can cause serious damage to the wine, and multiple uses of the same type of spray do not amplify the effect.

# Example

stdin

5 2
3 1
5 3 4 8 7


stdout

4


## Explanation

After one day: $3\ 4\ 5\ 7\ 8 \rightarrow 2\ 3\ 4\ 4\ 5$ (from rooms $4$ and $5$, $3$ bugs will be eliminated and from rooms $1,\ 2$ and $3$, $1$ bug)

After two days: $2\ 3\ 4\ 4\ 5 \rightarrow 1\ 2\ 3\ 1\ 2$ (from rooms $4$ and $5$, $3$ bugs will be eliminated and from rooms $1,\ 2$ and $3$, $1$ bug)

After tree days: $1\ 2\ 3\ 1\ 2 \rightarrow 0\ 1\ 0\ 0\ 0$ (from room $3$, $3$ bugs will be eliminated, from room $5$, $2$ bugs and from rooms $1,\ 2$ and $4$, $1$ bug)

After four days: $0\ 1\ 0\ 0\ 0 \rightarrow 0\ 0\ 0\ 0\ 0$ (from room $2$, $1$ bug will be eliminated)

## Problem info

ID: 1615

Editor: stefdasca

Author:

Source: IIOT 2019-20 Round I

Tags: