409860: GYM103811 D Double Queue

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?

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 a single integer, the minimum time required for Dan to buy the fruits (in seconds).

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

8

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.