##### IOI '09 - Plovdiv, Bulgaria

A parking garage has parking spaces, numbered from to
inclusive. The garage opens empty each morning and operates in the
following way throughout the day. Whenever a car arrives at the garage,
the attendants check whether there are any parking spaces available. If
there are none, then the car waits at the entrance until a parking space
is released. If a parking space is available, or as soon as one becomes
available, the car is parked in the available parking space. If there is
more than one available parking space, the car will be parked at the
space with the smallest number. If more cars arrive while some car is
waiting, they all line up in a queue at the entrance, in the order in
which they arrived. Then, when a parking space becomes available, the
first car in the queue (*i.e.*, the one that arrived the earliest) is
parked there.

The cost of parking in dollars is the weight of the car in kilograms multiplied by the specific rate of its parking space. The cost does not depend on how long a car stays in the garage.

The garage operator knows that today there will be cars coming and he knows the order of their arrivals and departures. Help him calculate how many dollars his revenue is going to be today.

Write a program that, given the specific rates of the parking spaces, the weights of the cars and the order in which the cars arrive and depart, determines the total revenue of the garage in dollars.

#### Input Specification

Your program must read from standard input the following data:

- The first line contains the integers and , separated by a space.
- The next lines describe the rates of the parking spaces. The
^{th}of these lines contains a single integer , the rate of parking space number in dollars per kilogram. - The next lines describe the weights of the cars. The cars are
numbered from 1 to inclusive in no particular order. The
^{th}of these lines contains a single integer , the weight of car in kilograms. - The next lines describe the arrivals and departures of all cars
in chronological order. A positive integer indicates that car
number arrives at the garage. A negative integer - indicates
that car number departs from the garage. No car will depart from
the garage before it has arrived, and all cars from 1 to
inclusive will appear exactly twice in this sequence, once arriving
and once departing. Moreover, no car will depart from the garage
before it has parked (
*i.e.*, no car will leave while waiting in the queue).

#### Output Specification

Your program must write to standard output a single line containing a single integer: the total number of dollars that will be earned by the garage operator today.

#### Sample Input 1

```
3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1
```

#### Sample Output 1

`5300`

#### Explanation for Sample Output 1

Car number 3 goes to space number 1 and pays dollars.

Car number 2 goes to space number 2 and pays dollars.

Car number 1 goes to space number 1 (which was released by car number 3) and pays dollars.

Car number 4 goes to space number 3 (the last remaining) and pays dollars.

#### Sample Input 2

```
2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4
```

#### Sample Output 2

`16200`

#### Explanation for Sample Output 2

Car number 3 goes to space number 1 and pays dollars.

Car number 1 goes to space number 2 and pays dollars.

Car number 2 arrives and has to wait at the entrance.

Car number 4 arrives and has to wait at the entrance behind car number 2.

When car number 1 releases its parking space, car number 2 parks there and pays dollars.

When car number 3 releases its parking space, car number 4 parks there and pays dollars.

#### Note on grading

For a number of tests worth 40 points, there will always be at least one available parking space for every arriving car. In these cases, no car will ever have to wait for a space.

## Comments

that parking is more expensive than downtown Toronto