Background

High school tasks are very heavy. You have to study ten subjects (in Zhejiang, you also study technology). This makes the amount of homework increase a lot, and this has already shown up during the summer vacation.

The total amount of homework is fixed, but the time when different homework is assigned is not fixed, so you need to spend different amounts of time dealing with homework each day. At this time, how to ensure enough sleep is a problem that needs careful consideration.

Problem Description

Hint: If you have questions about the statement, you can read it together with the samples to understand it better.

There are $n$ tasks. The $i$-th task needs $t_i$ time. Eric needs to finish these tasks in order over several days. Eric is a focused person, so the time spent on each task must be continuous.

A day has $x$ time. Because Eric needs to sleep, Eric cannot use all the time. Specifically:

• Eric must sleep every day.
• Eric’s sleeping time each day is continuous, and after the sleeping time ends, the next day starts immediately.
• The total sleeping time over the first $\boldsymbol i$ days cannot be less than $r \cdot x \cdot i$. Here $r$ is a given real number, and $i$ is a positive integer.

Eric asks you: at least how many days are needed to finish all tasks.

Input Format

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

The next line contains $n$ integers. The $i$-th integer is $t_i$.

Output Format

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

3 5 1 3
1 2 2

2

2 10 4 10
9 1

3

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

10

见下发文件 task/task4.in

见下发文件 task/task4.ans

见下发文件 task/task5.in

见下发文件 task/task5.ans

Hint

Sample 1 Explanation

Here is one possible plan:

Eric does task $1$ on the first day, spending $1$ time in total, and sleeps for $4$ time, which satisfies the requirement of at least $5 \times \dfrac 1 3 = \dfrac 5 3$ sleeping time.

Then on the second day, Eric works extra hard and finishes the remaining tasks, with $1$ time for sleep. The total sleeping time over two days is $5 \ge 10 \times \dfrac 1 3 = \dfrac {10} 3$, which also satisfies the requirement.

Sample 2 Explanation

Eric tries to finish task $1$ on the first day, but if he does it, he would have to stay up late and would not sleep enough. So Eric can only sleep all day on the first day. Finishing task $1$ on the second day is fine.

Also note that even if the sleeping time meets the requirement, Eric still cannot finish task $2$ on the second day, because Eric must sleep. So Eric sleeps until the third day, and then finishes task $2$. It can be proven that there is no plan using fewer than three days.

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

Sample 3 Explanation

Obviously, you can only do one task per day, so you need $10$ days.

Sample 4 Explanation

This sample satisfies the constraints of Subtask 3.

Sample 5 Explanation

This sample satisfies the constraints of Subtask 5.

Constraints and Conventions

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

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \bf 子任务 & \bf 分值 & n\le & \bf特殊性质 \\ \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,\ \dfrac{t_i}{x}+\dfrac{p}{q}\le 1$.

Special property $\bf B$: $n \times q \le 10^6$.

To reduce the evaluation workload, this problem enables subtask dependencies. Specifically, Subtask 5 is scored only when and only when all of the first four subtasks are passed; otherwise Subtask 5 is scored as $0$ points.

Translated by ChatGPT 5