Parking Lot

A downtown parking lot has $N$ parking spaces numbered from $1$ to $N$. Every morning the lot opens with all spaces empty, and throughout the day it operates by the following rules.

When a car arrives, the attendant checks whether any space is empty. If none is empty, the car waits at the entrance until a space frees up. As soon as a space becomes available (or one is already free on arrival), the car parks in it. If several spaces are free, the car parks in the one with the smallest number. When several cars arrive at once, they line up at the entrance in arrival order; the waiting line behaves like a queue, so the earliest-arriving car parks first.

The parking fee is proportional to the car's weight, not to the time parked. The fee equals the car's weight multiplied by the per-unit-weight rate of the space where it parks.

The attendant knows that $M$ cars will use the lot today, as well as the exact order in which the cars enter and leave.

Given the per-space rates, the weight of each car, and the enter/leave order, write a program that computes the total revenue the lot earns over the day.

• The first line contains two integers $N$ and $M$ separated by a space.
• Each of the next $N$ lines contains the per-unit-weight rate of a space. The $s$-th of these lines holds $R_s$, the per-unit-weight rate of space $s$.
• Each of the next $M$ lines contains the weight of a car. Cars are numbered $1$ through $M$, independent of the enter/leave order. The $k$-th of these lines holds $W_k$, the weight of car $k$.
• Each of the next $2M$ lines contains one integer describing the enter/leave order. A positive integer $i$ means car $i$ enters the lot; a negative integer $-i$ means car $i$ leaves the lot.

A car never leaves without having entered. Every car from $1$ to $M$ enters exactly once and leaves exactly once. A car waiting at the entrance never leaves without parking.

• $1 \le N \le 100$ (number of spaces)
• $1 \le M \le 2{,}000$ (number of cars)
• $1 \le R_s \le 100$ (per-unit-weight rate of space $s$)
• $1 \le W_k \le 10{,}000$ (weight of car $k$)

Print a single integer on one line: the total revenue the lot earns over the day.

For example, suppose the space rates are $2, 3, 5$; the car weights are $200, 100, 300, 800$; and the enter/leave order is $3, 2, -3, 1, 4, -4, -2, -1$. Then:

• Car $3$ parks in space $1$. Its fee is $300 \times 2 = 600$.
• Car $2$ parks in space $2$. Its fee is $100 \times 3 = 300$.
• Car $1$ parks in space $1$, freed by car $3$. Its fee is $200 \times 2 = 400$.
• Car $4$ parks in the last remaining space $3$. Its fee is $800 \times 5 = 4{,}000$.

The total revenue is $600 + 300 + 400 + 4{,}000 = 5{,}300$.