Parking#291
A parking lot has spaces, numbered from to . Each morning, the lot opens empty and operates as follows during the day. When a car arrives, the attendant checks if there are any available spaces. If there are none, the car waits at the entrance until a spot opens. If a space is available, or as soon as one becomes available, the car takes the smallest-numbered available spot. If several cars arrive when there is already a waiting queue, each newly arriving car joins the back of the queue, in the order of arrival. When a spot is freed, the first car in the queue (the one that has been waiting the longest) gets the spot.
The cost for a car to park is the product of its weight in kilograms and the rate per kilogram of its parking spot, in dollars. The duration of parking does not affect the cost.
The attendant knows in advance that cars will come today and knows the order in which every car both arrives and departs. Calculate the total revenue, in dollars, that the attendant will earn today.
The first line contains two integers (1 \leq n \leq 100) and (1 \leq m \leq 2000), separated by a space — the number of parking spaces and cars, respectively.
The next lines contain the rates for each parking space. The -th of these lines contains one integer r_s (1 \leq r_s \leq 100) — the rate for spot number in dollars per kilogram.
The following lines describe the weights of the cars. The cars are numbered from to in some order. The -th line contains one integer w_k (1 \leq w_k \leq 10000) — the weight, in kilograms, of car number .
The next lines describe the arrivals and departures in chronological order for all cars. A positive integer means car number arrives at the parking lot. A negative integer means car number departs. No car departs before arriving, and every car numbered through appears exactly twice in this sequence: once when arriving, and once when departing. Additionally, no car will depart before having been parked (that is, no car will leave from the queue).
Print one integer — the total number of dollars the attendant will earn today.
Example 1
Example 4