D. Double Queue
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dan would like to buy an apple from Alice's shop, and a banana from Bob's shop.

At time $$$0$$$, $$$Q_a$$$ customers suddenly appear and queue at Alice's shop, while $$$Q_b$$$ customers appear and queue at Bob's shop. Dan can choose to join in one of the queues right after those customers in negligible time.

It takes $$$S_a$$$ seconds for Alice to serve 1 customer, and $$$S_b$$$ seconds for Bob to serve 1 customer. Both Alice and Bob would handle customers on a first-come-first-serve basis. If Dan and other customers enter the queue at the same time, Dan will queue after those customers.

After buying a fruit, it takes $$$W$$$ seconds for Dan to walk from Alice's shop to Bob's shop, and vice versa.

Dan knows that there will be $$$N$$$ more customers coming to Alice's shop, and $$$M$$$ more customers coming to Bob's shop after time $$$0$$$. He also knows when they will enter the queue.

What is the minimum time required for Dan to buy an apple and a banana from the shops?

Input

The first line consists of 5 integers, $$$Q_a, Q_b, S_a, S_b, W$$$ ($$$0 \leq Q_a, Q_b \leq 10^5$$$, $$$1 \leq S_a, S_b, W \leq 100$$$).

The second line consists of 2 integers, $$$N, M$$$ ($$$1 \leq N, M \leq 10^5$$$).

The third line consists of $$$N$$$ integers, which is the time when new customers enter the queue for Alice's shop. The $$$i$$$-th integer correspond to $$$A_i$$$ ($$$1 \leq A_i \leq 10^6$$$).

The fourth line consists of $$$M$$$ integers, which is the time when new customers enter the queue for Bob's shop. The $$$i$$$-th integer correspond to $$$B_i$$$ ($$$1 \leq B_i \leq 10^6$$$).

It is guaranteed that $$$A_i$$$ and $$$B_i$$$ are sorted in non-descending order.

Output

Output a single integer, the minimum time required for Dan to buy the fruits (in seconds).

Example
Input
2 3 2 1 1
3 2
3 5 6
2 5
Output
8
Note

Dan can buy from both shops in $$$8$$$ seconds doing the following:

  • At time $$$0$$$, queue in Alice's shop after $$$2$$$ customers.
  • Wait for $$$4$$$ seconds to be served by Alice.
  • Takes $$$2$$$ seconds to buy an apple from Alice.
  • Walk to Bob's shop in $$$1$$$ second.
  • Get served immediately since no customers are queueing.
  • Takes $$$1$$$ seconds to buy a banana from Bob.
Total time used $$$= 4 + 2 + 1 + 1 = 8$$$.