题目背景

IOI2009 D2T1

题目描述

一个停车场有 $N$ 个停车位，依次编号为 $1$ 到 $N$。每天早上，停车场的所有停车位都是空的。当一辆车到达停车场时，服务员检查是否有空的停车位。如果没有，则这辆车将在入口处等待，直到有新的停车位。如果有，则这辆车将停在编号最小的空的停车位上。如果多辆车在入口处等待，则它们会按照到达的顺序排成队列，当出现空的停车位时，队列中的第一辆车（最早到达的车辆）将停在该停车位上。

每辆车的停车费是它的重量乘以对应停车位的特定比率，和它在停车场停了多久无关。

停车场管理员得知今天将有 $M$ 辆车前来停车，以及它们到达和离开的顺序。帮他计算今天的收入。

任务：编写一个程序，给定每个停车位的特定比率，每辆车的重量和所有车辆到达和离开的顺序，求出车库的总收入。

输入格式

第一行包含两个由空格隔开的整数 $N, M$，分别表示停车位数和车辆数。

接下来 $N$ 行描述了停车位的收费率。其中第 $s$ 行包含一个整数 $R_s$，表示编号为 $s$ 的停车位每千克收费的价格。

接下来 $M$ 行描述了车辆的重量。车辆从 $1$ 到 $M$ 编号，其中第 $k$ 行包含一个整数 $W_k$，表示编号为 $k$ 的车辆的重量，单位千克。

接下来 $2M$ 行描述了所有车辆到达和离开的时间顺序。一个正数 $i$ 表示编号为 $i$ 的车辆到达停车场。一个负数 $-i$ 表示编号为 $i$ 的车离开停车场。没有车辆会在到达之前离开停车场，且 $1\sim M$ 每辆车会在序列中出现恰好两次，一次到达，一次离开。此外，没有车辆会在停入停车场之前离开，也就是说，不会有队列中的车辆离开。

输出格式

一行一个整数，表示停车场管理员今天的收入。

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

提示

样例解释

• 样例 1：

  • 车辆 $3$ 停在车位 $1$，支付 $300\times 2 = 600$ 美元。
  • 车辆 $2$ 停在车位 $2$，支付 $100\times 3 = 300$ 美元。
  • 车辆 $1$ 停在车位 $1$（车辆 $3$ 空出的停车位），支付 $200\times 2 = 400$ 美元。
  • 车辆 $4$ 停在车位 $3$，支付 $800\times 5 = 4000$ 美元。

• 样例 2：

  • 车辆 $3$ 停在车位 $1$，支付 $1000\times 5 = 5000$ 美元。
  • 车辆 $1$ 停在车位 $2$，支付 $100\times 2 = 200$ 美元。
  • 车辆 $2$ 到达并在入口处等待。
  • 车辆 $4$ 到达并在入口处等待，排在车辆 $2$ 之后。
  • 当车辆 $1$ 离开时，车辆 $2$ 停在空出的车位 $2$，支付 $500\times 2 = 1000$ 美元。
  • 当车辆 $3$ 离开时，车辆 $4$ 停在空出的车位 $1$，支付 $2000\times 5 = 10000$ 美元。

数据范围与约定

• 对于 $40\%$ 的数据，没有车辆会在停车场等待。
• 对于 $100\%$ 的数据，$1\leq N\leq 100$，$1\leq M\leq 2000$，$1\leq R_s\leq 100$，$1\leq W_k\leq 10 ^ 4$。