Zane is traveling in a strange country. In this country, there are N provinces, which together form a straight line. We enumerate them from 1 to N, from left to right.

Zane is in province 1. He wants to visit each province exactly once, from 1 to N.

Zane is a phone addict. Hence, he must have the cell phone with non-negative battery charge throughout his journey. Initially, the battery in his phone has capacity X and is fully-charged. Once he travels from province i to province $i+1$ ($1 \le i < N$), the battery charge will decrease by $L[i]$.

Luckily, there is a battery shop in all provinces. In province i ($1 \le i < N$), there is a fully-charged battery with capacity $C[i]$ for sale at $P[i]$ dollars. If Zane decides to buy it, he may use it to replace his cell phone battery. Because Zane doesn’t want to carry too many items with him while traveling, he will not carry more than one battery at the same time, which is the one installed in his cell phone. He may throw away the battery he does not want at any time.

You will be given M questions, each denoted by one integer c. The answer to each question is the minimum money, in dollars, Zane needs to complete his journey when $X = c$. If there is no valid journey, the answer is considered to be $-1$.

Input
The first line consists of two integers N and M denoting the number of provinces and the number of questions.
The second line consists of $N-1$ integers, the i-th of which denotes $L[i]$.
The third line consists of $N-1$ integers, the i-th of which denotes $C[i]$.
The fourth line consists of $N-1$ integers, the i-th of which denotes $P[i]$.
The fifth line consists of M integers, the i-th of which denotes the parameter c of the i-th question.

Output
Print M lines, the i-th of which contains one integer that is the answer to the i-th question.

Constraints
$2 \le N, M \le 300,000$
$1 \le L[i], C[i], P[i] \le 300,000$
$1 \le c \le 10^{18}$