Background

IOI 2009 D2T1.

Problem Description

A parking garage has $N$ parking spaces, numbered from $1$ to $N$ in order. Every morning, all parking spaces in the garage are empty. When a car arrives at the garage, the attendant checks whether there is an empty parking space. If there is none, the car waits at the entrance until a new space becomes available. If there is an empty space, the car is parked in the empty space with the smallest number. If multiple cars are waiting at the entrance, they form a queue in the order they arrived. When a parking space becomes available, the first car in the queue (the earliest-arriving car) will be parked in that space.

The parking fee for each car is its weight multiplied by the specific rate of the parking space it uses, and it does not depend on how long the car stays in the garage.

Task: Write a program that, given the specific rate of each parking space, the weight of each car, and the arrival and departure order of all cars, computes the total income of the garage.

Input Format

The first line contains two integers $N, M$ separated by spaces, representing the number of parking spaces and the number of cars.

The next $N$ lines describe the rates of the parking spaces. Line $s$ contains an integer $R_s$, meaning the price charged per kilogram for parking space $s$.

The next $M$ lines describe the weights of the cars. Cars are numbered from $1$ to $M$. Line $k$ contains an integer $W_k$, meaning the weight of car $k$ in kilograms.

The next $2M$ lines describe the time order of all arrivals and departures. A positive number $i$ indicates that car $i$ arrives at the garage. A negative number $-i$ indicates that car $i$ leaves the garage. No car will leave before it arrives. Each car in $1\sim M$ appears exactly twice in the sequence: once for arrival and once for departure. Also, no car will leave before it has been parked in the garage, which means no car leaves while waiting in the queue.

Output Format

Output one integer on a single line, representing the income of the garage manager for today.

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

5300

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

16200

Hint

Sample Explanation

• Sample 1:

  • Car $3$ parks in space $1$ and pays $300\times 2 = 600$ dollars.
  • Car $2$ parks in space $2$ and pays $100\times 3 = 300$ dollars.
  • Car $1$ parks in space $1$ (the space freed by car $3$) and pays $200\times 2 = 400$ dollars.
  • Car $4$ parks in space $3$ and pays $800\times 5 = 4000$ dollars.

• Sample 2:

  • Car $3$ parks in space $1$ and pays $1000\times 5 = 5000$ dollars.
  • Car $1$ parks in space $2$ and pays $100\times 2 = 200$ dollars.
  • Car $2$ arrives and waits at the entrance.
  • Car $4$ arrives and waits at the entrance, behind car $2$ in the queue.
  • When car $1$ leaves, car $2$ parks in the freed space $2$ and pays $500\times 2 = 1000$ dollars.
  • When car $3$ leaves, car $4$ parks in the freed space $1$ and pays $2000\times 5 = 10000$ dollars.

Constraints and Notes

• For $40\%$ of the testdata, no car will have to wait in the garage.
• For $100\%$ of the testdata, $1\leq N\leq 100$, $1\leq M\leq 2000$, $1\leq R_s\leq 100$, $1\leq W_k\leq 10 ^ 4$.

Translated by ChatGPT 5