Two groups of market participants are actively trading futures in the chaotic Egyptian stock market. One group are the naive retail investors who try to make a quick buck, but tend to lose money rather than make any profit. The other group is really just one person: trader extraordinaire Maged from Sphinx Trading. Maged is bringing in billions for Sphinx Trading, and these record profits are raising suspicions among the trading community. Majid from Nile River Capital is especially sceptical, and raises what he believes are questionable market movements to the Egyptian authorities.

Currently, there are ~n~ types of futures contracts in the market. For each type ~t~, there are ~c_t~ contracts available, where each contract has a value of ~v_t~ dollars.

The groups of market participants take turns trading for a total of ~m~ rounds, with the group of retail investors starting first. In the ~i~th round, the current participant trades exactly ~q_i~ contracts in the market (across any type, without exceeding availability).

As a seasoned trader, Maged makes optimal trades to maximise his profits. The naive group of retail investors, despite thinking they're making optimal trades, end up trading the least valuable contracts, effectively minimising their potential gains.

The market regulators have called upon you to determine whether any suspicious behaviour is taking place by computing the total value of all remaining futures contracts after all ~m~ rounds. This information will be vital in determining if Maged is suspiciously moving markets!

Input

The first line contains two integers ~n~ ~(1 \le n \le 10^5)~ and ~m~ ~(1 \le m \le 100)~, the number of contract types and the number of turns trading, respectively.

The second line contains ~n~ space-separated integers ~c_t~ ~(1 \leq c_t \leq 10^5)~, the number of contracts available for a futures contract of type ~t~.

The third line contains ~n~ space-separated integers ~v_t~ ~(1 \leq v_t \leq 10^5)~, the value of the contract of type ~t~.

The last line contains ~m~ space-separated integers ~q_i~ ~(0 \leq q_i \leq 10^5)~, the quantity of contracts traded on the ~i~th turn.

Output

Print the total value of all remaining futures contracts after ~m~ rounds.

Examples

Input 1

4 4
2 1 2 4
2 2 4 4
1 2 2 1

Output 1

12

Explanation

• On the first turn, the group of retail investors trade ~1~ contract worth ~$2~, trading the least valuable contracts.
• On the second turn, Maged trades ~2~ contracts worth ~$4~.
• Then, the group of retail investors trade ~2~ contracts worth ~$2~.
• Finally, Maged trades ~1~ contract worth ~$4~.

At the end of trading, there are ~3~ remaining contracts worth ~$4~ each, resulting in a total remaining value of ~$12~.

Input 2

4 2
1 1 2 8
4 1 2 5
1 2

Output 2

38