Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Helikopter Helikopter

By longlongint · Limits 1.5s, 512 MB


Tommy Vercetti has completed the infamous RC helicopter mission after many attempts. And now he needs your help flying a real helicopter.

There are MM bombs and NN helipads. And there is one Helikopter. Initially all bombs, the Helikopter and Tommy Vercetti are at helipad number 11. All the bombs need to be transported to helipad NN. Each bomb ii from 11 to MM has a weight of WiW_i.

There is a customs officer on each helipad. Officer ii will check the cargo of a Helikopter if and only if the cargo weight exceeds CiC_i while landing on helipad ii. Tommy does not want to be caught carrying bombs. And that is why his friend Lance Vance ওরফে কালা জাহাঙ্গীর has built hiding compartments in each helipad to store bombs temporarily.

The following rules are applicable for flying the Helikopter:

  1. Taking off from helipad ii, the Helikopter must land at helipad i+1i+1 or i1i-1, which takes 11 unit of time.

  2. Helikopter can carry any number of bombs.

  3. While parked on a helipad, Helikopter can drop or pickup any number of bombs from the hiding compartment instantaneously.

If it is possible to transport all bombs to helipad NN (without Tommy getting caught of course) then print the minimum time in which it can be done. Otherwise print -1.

Input

Input is given from Standard Input in the following format:

NN

C1C2CNC_1 C_2 … C_N

MM

W1W2WMW_1 W_2 … W_M

Constraints

  • 2N5×1052 \leq N \leq 5 \times 10^5

  • 1M151 \leq M \leq 15

  • 1Wi,Ci10151 \leq W_i, C_i \leq 10^{15}

Output

Print the answer.

Samples

InputOutput
2 
10 1
1
2
-1

Tommy will be caught by the officer of helipad NN.

InputOutput
5
20 20 20 20 20
3
5 5 5
4

Helikopter takes all bombs together in one go.

InputOutput
3
1 1 1
3
1 1 1
10

Helikopter takes bomb 11 from 11 to NN and then comes back to 11\rightarrow 44 moves. (During this, bomb number 22 and 33 are in hiding compartment of helipad 11)

Helikopter takes bomb 22 from 11 to NN and then comes back to 11\rightarrow 44 moves. (During this, bomb number 33 is in hiding compartment of helipad 11)

Helikopter takes bomb 33 from 11 to NN \rightarrow 22 moves.

Total 1010 moves.


Here is a song to help you visualize the problem.

Helikopter, helikopter
Para kofer, para kofer

Helikopter, helikopter
Šaljem ako treba
Para kofer, para kofer
Da bacaš sa neba
Helikopter, helikopter
Kol’ko treba zlata
Samo da od doma otvoriš mi vrata?

Majko moja, kakva je
Stvorena je za mene
Majko moja, vidi je
Vrh ljepote, takva je

Ne postoji blago to
A ni cijena ta
Na koju ne pristajem
Da je imam ja

Helikopter, helikopter
Šaljem ako treba
Para kofer, para kofer
Da bacaš sa nеba
Helikopter, helikoptеr
Kol’ko treba zlata
Samo da od doma otvoriš mi vrata?

Kao da je dragi Bog
Baš za sebe stvorio
Moje oko nikad ljepšu
Od nje nije vidjelo

Ne postoji blago to
A ni cijena ta
Na koju ne pristajem
Da je imam ja

Helikopter, helikopter
Šaljem ako treba
Para kofer, para kofer
Da bacaš sa neba
Helikopter, helikopter
Kol’ko treba zlata
Samo da od doma otvoriš mi vrata?

Discussion

Statistics


100% Solution Ratio

fsshakkhorEarliest, 2M ago

shefinFastest, 0.3s

shefinLightest, 8.4 MB

adnan_tokyShortest, 1786B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.