{"problem":{"name":"[IOI 2009] Garage","description":{"content":"一个停车场有 $N$ 个停车位，依次编号为 $1$ 到 $N$。每天早上，停车场的所有停车位都是空的。当一辆车到达停车场时，服务员检查是否有空的停车位。如果没有，则这辆车将在入口处等待，直到有新的停车位。如果有，则这辆车将停在编号最小的空的停车位上。如果多辆车在入口处等待，则它们会按照到达的顺序排成队列，当出现空的停车位时，队列中的第一辆车（最早到达的车辆）将停在该停车位上。 每辆车的停车费是它","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":32768},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9115"},"statements":[{"statement_type":"Markdown","content":"一个停车场有 $N$ 个停车位，依次编号为 $1$ 到 $N$。每天早上，停车场的所有停车位都是空的。当一辆车到达停车场时，服务员检查是否有空的停车位。如果没有，则这辆车将在入口处等待，直到有新的停车位。如果有，则这辆车将停在编号最小的空的停车位上。如果多辆车在入口处等待，则它们会按照到达的顺序排成队列，当出现空的停车位时，队列中的第一辆车（最早到达的车辆）将停在该停车位上。\n\n每辆车的停车费是它的重量乘以对应停车位的特定比率，和它在停车场停了多久无关。\n\n停车场管理员得知今天将有 $M$ 辆车前来停车，以及它们到达和离开的顺序。帮他计算今天的收入。\n\n**任务**：编写一个程序，给定每个停车位的特定比率，每辆车的重量和所有车辆到达和离开的顺序，求出车库的总收入。\n\n## Input\n\n第一行包含两个由空格隔开的整数 $N, M$，分别表示停车位数和车辆数。\n\n接下来 $N$ 行描述了停车位的收费率。其中第 $s$ 行包含一个整数 $R_s$，表示编号为 $s$ 的停车位每千克收费的价格。\n\n接下来 $M$ 行描述了车辆的重量。车辆从 $1$ 到 $M$ 编号，其中第 $k$ 行包含一个整数 $W_k$，表示编号为 $k$ 的车辆的重量，单位千克。\n\n接下来 $2M$ 行描述了所有车辆到达和离开的时间顺序。一个正数 $i$ 表示编号为 $i$ 的车辆到达停车场。一个负数 $-i$ 表示编号为 $i$ 的车离开停车场。没有车辆会在到达之前离开停车场，且 $1\\sim M$ 每辆车会在序列中出现恰好两次，一次到达，一次离开。此外，没有车辆会在停入停车场之前离开，也就是说，不会有队列中的车辆离开。\n\n## Output\n\n一行一个整数，表示停车场管理员今天的收入。\n\n[samples]\n\n## Background\n\nIOI2009 D2T1\n\n## Note\n\n### 样例解释\n\n- 样例 1：\n  - 车辆 $3$ 停在车位 $1$，支付 $300\\times 2 = 600$ 美元。\n  - 车辆 $2$ 停在车位 $2$，支付 $100\\times 3 = 300$ 美元。\n  - 车辆 $1$ 停在车位 $1$（车辆 $3$ 空出的停车位），支付 $200\\times 2 = 400$ 美元。\n  - 车辆 $4$ 停在车位 $3$，支付 $800\\times 5 = 4000$ 美元。\n\n- 样例 2：\n  - 车辆 $3$ 停在车位 $1$，支付 $1000\\times 5 = 5000$ 美元。\n  - 车辆 $1$ 停在车位 $2$，支付 $100\\times 2 = 200$ 美元。\n  - 车辆 $2$ 到达并在入口处等待。\n  - 车辆 $4$ 到达并在入口处等待，排在车辆 $2$ 之后。\n  - 当车辆 $1$ 离开时，车辆 $2$ 停在空出的车位 $2$，支付 $500\\times 2 = 1000$ 美元。\n  - 当车辆 $3$ 离开时，车辆 $4$ 停在空出的车位 $1$，支付 $2000\\times 5 = 10000$ 美元。\n\n### 数据范围与约定\n\n- 对于 $40\\%$ 的数据，没有车辆会在停车场等待。\n- 对于 $100\\%$ 的数据，$1\\leq N\\leq 100$，$1\\leq M\\leq 2000$，$1\\leq R_s\\leq 100$，$1\\leq W_k\\leq 10 ^ 4$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9115","tags":["2009","IOI","O2优化"],"sample_group":[["3 4\n2\n3\n5\n200\n100\n300\n800\n3\n2\n-3\n1\n4\n-4\n-2\n-1\n","5300\n"],["2 4\n5\n2\n100\n500\n1000\n2000\n3\n1\n2\n4\n-1\n-3\n-2\n-4\n","16200"]],"created_at":"2026-03-03 11:09:25"}}