Problem B
Bustling Busride

A crowded bus. By: Pexels/Pew Nguyen

It is Friday afternoon, $4$ PM, and as always, all the students want to go home, leading to quite a long queue at the bus stop. Fortunately, the bus line is served in regular intervals, with the first bus arriving at $4$ PM.

Whenever a bus arrives at the university, everyone in the queue tries to enter the bus, which makes the buses very crowded. This has led to numerous complaints where people tried to exit buses but were unable to because of the sheer amount of people. As a consequence, the bus company decided that at every stop which someone in the bus has as destination, everyone in the bus must exit it. Those who want to travel further enter again. For every time a passenger enters or exits the bus, the bus needs to wait $w$ seconds.

To offer the best service, the bus company wants to minimize the maximum time it takes anybody from 4 PM until they reach their destination. For each bus, the bus driver can decide how many people from the front of the queue enter the bus. The number of people that can enter a bus is unlimited. Help the bus drivers make the optimal decisions to achieve the company’s goal.

Input

The input consists of:

• One line with four integers $n$, $b$, $r$, and $w$ ($1\leq n, b \leq 10^5$, $1\leq r, w \leq 10^6$), the number of passengers, the number of bus stops, the time between the arrival of two buses at the university, and the delay for exiting and entering.

• One line with $b$ integers $d_{i}$ ($1 \le d_{i}, \sum d_{i} \leq 10^6$), the travel time from the $(i-1)$th bus stop to the $i$th bus stop (the $0$th bus stop is the university).

• One line with $n$ integers $t_{i}$ ($1 \leq t_{i} \leq b$), indicating that the destination of the $i$th person in line is the $t_i$th bus stop.

All times are given in seconds.

Output

Output the minimum number of seconds until every person in line has exited at their destination.

Notes

In the first sample, it is optimal to let everyone board the first bus. The first boarding takes 3 seconds. Then, the bus drives for 2 seconds to get to the bus stop 1. After 3 seconds, everybody exited and after another 2 seconds, the people continuing their journey are back on the bus. After 2 more seconds, they arrive at the next stop where it takes 2 seconds for everybody to exit and one second for the remaining person to get back on the bus. After 2 more seconds, the bus arrives at the final destination where it takes one second for the last person to exit.

In the second sample, it is optimal to use one bus per person.

In the third sample, it is optimal to assign the first two passengers to one bus. Everybody else gets their own bus.

3 3 20 1
2 2 2
2 3 1

18

4 2 1 10
3 2
1 2 2 1

27

5 3 3 3
2 2 1
3 3 2 1 1

17