Парковка
Парковка
Парковка имеет n мест, пронумерованных от 1 до n включительно. Парковка открывается пустой каждое утро и работает на протяжении дня следующим образом. Когда автомобиль приезжает на парковку, парковщик проверяет, есть ли свободные места. Если таковых нет, автомобиль ожидает возле въезда до тех пор, пока освободится какое-то место. Если есть свободное место, или как только оно освобождается, автомобиль занимает свободное парковочное место. Если есть несколько свободных парковочных мест, автомобиль занимает место с наименьшим номером. Когда приезжают парковаться другие автомобили, но уже есть ожидающий автомобиль, они выстраиваются в очередь на въезде в том порядке, в котором приехали. После того, как освобождается парковочное место, его занимает первый автомобиль из очереди (то есть тот, который прибыл парковаться первым).
Стоимость парковки одного автомобиля в долларах определяется как произведение веса этого автомобиля в килограммах на тариф его парковочного места. Стоимость парковки автомобиля не зависит от того, сколько времени этот автомобиль находится на парковке.
Парковщик знает, что сегодня на парковку приедет m автомобилей, и он знает порядок их приезда и отъезда. Помогите ему подсчитать, сколько долларов он сегодня заработает.
Напишите программу, которая по заданным тарифам парковочных мест, весам автомобилей и порядку, в котором автомобили приезжают и уезжают, определяет доход парковки в долларах.
Входные данные
Первая строка содержит два целых числа - количество парковочных мест n (1 ≤ n ≤ 100) и количество автомобилей m (1 ≤ m ≤ 2000), разделенные пробелом.
Следующие n строк описывают тарифы парковочных мест, s-ая из этих строк содержит одно целое число rs
(1 ≤ rs
≤ 100) - тариф парковочного места с номером s в долларах за килограмм.
Следующие m строк описывают веса автомобилей. Автомобили пронумерованы в произвольном порядке от 1 до m включительно, k-ая из этих m строк содержит одно целое число wk
(1 ≤ wk
≤ 10000) – вес автомобиля с номером k в килограммах.
Следующие 2m строк описывают приезд и выезд всех автомобилей в хронологическом порядке. Положительное целое число i показывает, что автомобиль с номером i приезжает на парковку. Отрицательное целое число -i показывает, что автомобиль с номером i уезжает с парковки. Никакой автомобиль не выезжает с парковки до своего приезда, и все автомобили от 1 до m включительно появятся в этой последовательности строк ровно 2 раза, один раз как приезжающий, и второй – как выезжающий. К тому же, никакой из автомобилей не выедет с парковки, пока не займет место на парковке (то есть, никакой автомобиль не уедет пока стоит в очереди).
Выходные данные
Вывести одно целое число - общее количество долларов, которое заработает сегодня парковщик.
3 4 2 3 5 200 100 300 800 3 2 -3 1 4 -4 -2 -1
5300
4 4 8 8 2 2 8 9 9 6 2 4 1 3 -3 -4 -2 -1
154