Exam

Time limit1sMemory limit1024 MB

Summary

Given N easy or hard problems with mandatory times t_i, find the leave time and solved set that maximize points without leaving any mandatory problem unsolved.

Level: Medium6 of 10
Topics: Greedy, Sorting, Prefix sum
Solved: No attempts yet

Problem

Joonatan has to take a math exam and wants to score as many points as possible. He studied the rules carefully to find out how to pass the exam.

The exam has $N$ problems, and Joonatan has $T$ minutes to solve them. The exam starts at time $0$ and ends at time $T$ . He may leave the exam at any integer time from $0$ to $T$ .

There are two kinds of problems: easy and hard. An easy problem takes exactly $A$ minutes to solve, and a hard problem takes exactly $B$ minutes. If he starts an easy problem at time $x$ , he finishes it at time $x + A$ . If he starts a hard problem at time $y$ , he finishes it at time $y + B$ . For each problem, it is known whether it is easy or hard. Solving a hard problem always takes more time than solving an easy one. Joonatan can solve only one problem at a time.

Each problem $i$ also has a time $t_i$ , from which that problem becomes mandatory. If Joonatan leaves the exam at time $s$ and some problem $i$ with $t_i \le s$ is not solved, he gets $0$ points for the whole exam. Otherwise he gets one point for each solved problem. When he leaves at time $s$ , he may have solved both mandatory problems and problems that are not yet mandatory.

Find the maximum number of points Joonatan can get on this exam.

Input

The first line contains four integers separated by spaces: $N$ ( $2 \le N \le 5 \cdot 10^5$ ), $T$ ( $1 \le T \le 10^9$ ), $A$ , and $B$ ( $1 \le A < B \le 10^9$ ).

The second line contains $N$ integers. The $i$ -th number is $0$ if problem $i$ is easy, and $1$ if it is hard.

The third line contains $N$ integers $t_i$ ( $0 \le t_i \le T$ ). The $i$ -th number is the time at which problem $i$ becomes mandatory.

Output

Print one integer: the maximum number of points Joonatan can get on this exam.

Examples3

Example 1
Input
```
2 5 2 3
1 0
3 2
```
Expected output
```
2
```

Example 2

Input

6 20 3 6
0 1 0 0 1 0
20 11 3 20 16 17

Expected output

Example 3
Input
```
6 20 2 5
1 1 0 1 0 0
0 8 2 9 11 6
```
Expected output
```
0
```