Problem Background

High school tasks are extremely demanding, involving the study of ten subjects (technology is also included in Zhejiang province). This leads to a significant increase in homework, which is already evident during the summer vacation.

The total amount of homework is fixed, but the timing of when different assignments are issued varies, resulting in different amounts of time needed each day to cope with them. Ensuring adequate sleep becomes a critical issue to consider.

Problem Description

Hint: If you have questions about the problem content, reading the sample cases may help you better understand it.

There are $n$ tasks, with the $i$-th task requiring $t_i$ time. Eric needs to complete these tasks in order over several days. Eric is focused, so the time taken to complete each task must be continuous.

A day has $x$ hours. Since Eric needs to sleep, he cannot use all the time available. Specifically:

• Eric must sleep every day;
• Eric's sleep time is continuous, and after waking up, the next day begins;
• The total sleep time for the first $i$ days must not be less than $r \cdot x \cdot i$ hours. $r$ is a given real number, and $i$ is a positive integer.

Eric wants to know the minimum number of days required to complete all tasks.

Input Format

The first line contains four integers $n, x, p, q$, where $r = \frac{p}{q}$.

The next line contains $n$ integers, with the $i$-th integer representing $t_i$.

Output Format

Output a single positive integer representing the minimum number of days. It can be proven that under the given constraints, there is always at least one solution.

Sample Input and Output

Sample Input #1

3 5 1 3
1 2 2

Sample Output #1

2

Sample Input #2

2 10 4 10
9 1

Sample Output #2

3

Sample Input #3

10 2 1 2
1 1 1 1 1 1 1 1 1 1

Sample Output #3

10

Sample Input #4

See the provided file task/task4.in

Sample Output #4

See the provided file task/task4.ans

Sample Input #5

See the provided file task/task5.in

Sample Output #5

See the provided file task/task5.ans

Notes

Sample 1 Explanation

One possible plan:

Eric completes task 1 on the first day, using 1 hour and sleeping for 4 hours, meeting the requirement of at least $5 \times \frac{1}{3} = \frac{5}{3}$ hours of sleep.

On the second day, Eric works hard to complete the remaining tasks, sleeping for 1 hour. The total sleep over two days is $5 \geq 10 \times \frac{1}{3} = \frac{10}{3}$, which also meets the requirement.

Sample 2 Explanation

Eric tries to complete task 1 on the first day, but if he does, he will stay up late and not get enough sleep. So, Eric can only sleep on the first day. On the second day, Eric completes task 1 without any issues.

Note that even if the sleep requirement is met, Eric cannot complete task 2 on the second day because he must sleep. So, Eric sleeps until the third day and then completes task 2. It can be proven that there is no solution in fewer than three days.

Also, note that the data does not guarantee $\gcd(p, q) = 1$.

Sample 3 Explanation

Clearly, only one task can be done in a day, so it takes 10 days.

Sample 4 Explanation

This sample meets the constraints of Subtask 3.

Sample 5 Explanation

This sample meets the constraints of Subtask 5.

Data Size and Constraints

This problem is bundled testing. For all data, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq t_i < x \leq 10^6$, $1 \leq p < q \leq 10^6$.

$$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \bf Subtask & \bf Points & n \le & \bf Special Properties \\ \hline 1 & 10 & 3 & / \\\hline 2 & 20 & 10^3 & \bf A \\\hline 3 & 20 & / & \bf A \\\hline 4 & 20 & / & \bf B \\\hline 5 & 30 & / & / \\\hline \end{array} $$

Special Property $\bf A$: $\forall i, \frac{t_i}{x} + \frac{p}{q} \leq 1$.

Special Property $\bf B$: $n \times q \leq 10^6$.

To reduce evaluation efforts, this problem has subtask dependencies. Specifically, Subtask 5 will only be scored if the first four subtasks are all passed; otherwise, Subtask 5 will score 0 points.

见题面 Input 部分

见题面 Output 部分