Парковка
Парковка имеет n мест, пронумерованных от 1 до n включительно. Парковка открывается пустой каждое утро и работает на протяжении дня следующим образом. Когда автомобиль приезжает на парковку, парковщик проверяет, есть ли свободные места. Если таковых нет, автомобиль ожидает возле въезда до тех пор, пока освободится какое-то место. Если есть свободное место, или как только оно освобождается, автомобиль занимает свободное парковочное место. Если есть несколько свободных парковочных мест, автомобиль занимает место с наименьшим номером. Когда приезжают парковаться другие автомобили, но уже есть ожидающий автомобиль, они выстраиваются в очередь на въезде в том порядке, в котором приехали. После того, как освобождается парковочное место, его занимает первый автомобиль из очереди (то есть тот, который прибыл парковаться первым).
Стоимость парковки одного автомобиля в долларах определяется как произведение веса этого автомобиля в килограммах на тариф его парковочного места. Стоимость парковки автомобиля не зависит от того, сколько времени этот автомобиль находится на парковке.
Парковщик знает, что сегодня на парковку приедет m автомобилей, и он знает порядок их приезда и отъезда. Помогите ему подсчитать, сколько долларов он сегодня заработает.
Напишите программу, которая по заданным тарифам парковочных мест, весам автомобилей и порядку, в котором автомобили приезжают и уезжают, определяет доход парковки в долларах.
Входные данные
Первая строка содержит два целых числа - количество парковочных мест n (1 ≤ n ≤ 100) и количество автомобилей m (1 ≤ m ≤ 2000), разделенные пробелом.
Следующие n строк описывают тарифы парковочных мест, s-ая из этих строк содержит одно целое число r[s] (1 ≤ r[s] ≤ 100) - тариф парковочного места с номером s в долларах за килограмм.
Следующие m строк описывают веса автомобилей. Автомобили пронумерованы в произвольном порядке от 1 до m включительно, k-ая из этих m строк содержит одно целое число w[k] (1 ≤ w[k] ≤ 10000) – вес автомобиля с номером k в килограммах.
Следующие 2m строк описывают приезд и выезд всех автомобилей в хронологическом порядке. Положительное целое число i показывает, что автомобиль с номером i приезжает на парковку. Отрицательное целое число -i показывает, что автомобиль с номером i уезжает с парковки. Никакой автомобиль не выезжает с парковки до своего приезда, и все автомобили от 1 до m включительно появятся в этой последовательности строк ровно 2 раза, один раз как приезжающий, и второй – как выезжающий. К тому же, никакой из автомобилей не выедет с парковки, пока не займет место на парковке (то есть, никакой автомобиль не уедет пока стоит в очереди).
Выходные данные
Вывести одно целое число - общее количество долларов, которое заработает сегодня парковщик.