Парковка#291

Парковка

1 секунда

128 мегабайтів

Дуже легка

Парковка має $n$ місць, пронумерованих від $1$ до $n$ включно. Парковка відкривається порожньою щоранку і працює протягом дня наступним чином. Коли автомобіль приїжджає на парковку, паркувальник перевіряє, чи є вільні місця. Якщо таких немає, автомобіль чекає біля в'їзду до тих пір, поки звільниться якесь місце. Якщо є вільне місце, або як тільки воно звільняється, автомобіль займає вільне місце для паркування. Якщо є кілька вільних паркувальних місць, автомобіль займає місце з найменшим номером. Коли приїжджають паркуватися інші автомобілі, але вже є автомобіль, що очікує, вони шикуються в чергу на в'їзді в тому порядку, в якому приїхали. Після того, як звільняється паркувальне місце, його займає перший автомобіль з черги (тобто той, який прибув паркуватися першим).

Вартість паркування одного автомобіля в доларах визначається як добуток ваги цього автомобіля в кілограмах на тариф його паркувального місця. Вартість паркування автомобіля не залежить від того, скільки часу цей автомобіль знаходиться на парковці.

Паркувальник знає, що сьогодні на парковку приїде $m$ автомобілів, і він знає порядок їх приїзду та від'їзду. Допоможіть йому підрахувати, скільки доларів він заробить сьогодні.

Напишіть програму, яка за заданими тарифами паркувальних місць, вагами автомобілів та порядком, в якому автомобілі приїжджають і виїжджають, визначає прибуток паркувальника в доларах.

Вхідні дані

Перший рядок містить два цілі числа — кількість паркувальних місць $n$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100) та кількість автомобілів $m$ ( $1 \leq m \leq 2000$ 1 \leq m \leq 2000), розділених проміжком.

Наступні $n$ рядків описують тарифи паркувальних місць, $s$ -ий з цих рядків містить одне ціле число $r_{s}$ r_s ( $1 \leq r_{s} \leq 100$ 1 \leq r_s \leq 100) — тариф паркувального місця з номером $s$ у доларах за кілограм.

Наступні $m$ рядків описують ваги автомобілів. Автомобілі пронумеровані в довільному порядку від $1$ до $m$ включно, $k$ -ий з цих $m$ рядків містить одне ціле число $w_{k}$ w_k ( $1 \leq w_{k} \leq 10000$ 1 \leq w_k \leq 10000) — вагу автомобіля з номером $k$ в кілограмах.

Наступні $2 m$ рядків описують приїзд та виїзд усіх автомобілів в хронологічному порядку. Додатне ціле число $i$ показує, що автомобіль з номером $i$ приїжджає на парковку. Від'ємне ціле число $- i$ показує, що автомобіль з номером $i$ їде з парковки. Жодний автомобіль не виїжджає з парковки до свого приїзду, і всі автомобілі від $1$ до $m$ включно з'являться в цій послідовності рядків рівно $2$ рази, один раз як приїжджає, і другий — як виїжджає. До того ж, жоден з автомобілів не виїде з парковки, поки не займе місце на парковці (тобто, жодний автомобіль не виїде, поки стоїть у черзі).

Вихідні дані

Виведіть одне ціле число — загальну кількість доларів, яку заробить сьогодні паркувальник.

Приклади

Приклад 1

Приклад 4