Problem : 268 - Garage

Problem Statistics

Solved Member: 27　　Submission: 49　　User Tried: 28

Statement:

某停車場共有編號從 1 到 N 的 N 個停車位，停車場每天早上營運前都沒有車，並且每天依照下列的方式運作。當有車子抵達停車場時，管理員會先確認目前是否還有空餘的停車位。如果沒有空位，這輛車必須在入口處等待，直到有空餘的停車位出現為止。如果還有空位，或一旦有空位產生，這輛車將停入此空位中。如果有超過一個空餘的停車位，這輛車將停入編號最小的停車位。如果當有車子在等待時，還有其他車子抵達，那麼這些車子將依照他們抵達的先後順序排列。然後，一旦有停車位空位出現，佇列中的第一輛車 ( 亦即最先到達的車 ) 將會停入這個空位。

停車費以元為單位，計算方式是用車子的重量 (公斤重) 乘以停車位的費率。停車費與停車時數無關。

停車場的管理員知道今天將有 M 台車前來停車，並且知道他們抵達和離開的順序，請幫忙他計算今天收入的金額。

Task:

給定停車位的費率、車子的重量和他們抵達與離開的順序，請寫一個程式來計算停車場的總收入。

Input:Output:

第一行含有整數 N 和 M，中間以一個空白隔開。

接下來的 N 行描述停車位的費率。其中第 s 行含有一個整數 R_s，表示第 s 個停車位的費率 (單位：元/公斤) 。

接下來的 M 行描述車輛的重量。這些車子分別由 1 到 M 加以編號 ( 並無特定的順序 )。這 M 行中的第 k 行含有一個整數 W_k，代表第 k 輛車的重量 (單位：公斤) 。

接下來的 2*M 行，依照時間先後順序，描述所有車子的抵達和離開。正整數 i 代表編號 i 的車輛抵達停車場。負整數 -i 代表編號 i 的車輛離開停車場。沒有車輛會在抵達前離開停車場，且所有編號從 1 到 M 的車輛會在此序列中正好出現兩次，其中一次為抵達，另一次為離開。另外，沒有車子會再停好車前就先離開 ( 亦即沒有車子會在住列中等待時離開 ) 。

限制：
1 ≤ N ≤ 100，停車位數目。
1 ≤ M ≤ 2000，車輛數。
1 ≤ R_s ≤ 100，停車位 s 的費率 ( 單位：元/公斤 )
1 ≤ W_k ≤ 10000，車輛 k 的重量 ( 單位：公斤 )

輸出一個整數表示今日停車場管理員的總收入。

Sample Input:Sample Output:

Sample #1:
3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1

Sample #2:
2 4
5
2
100
500
1000
2000
3
1
2
4
-1
-3
-2
-4

Sample #1:
5300

Sample #2:
16200

HINT:

Sample #1:
編號 3 的車輛停入 1 號停車位，並且付 300*2 = 600 元。
編號 2 的車輛停入 2 號停車位，並且付 100*3 = 300 元。
編號 1 的車輛停入 1 號停車位 (之前編號 3 的車輛使用過)，並且付 200*2 = 400 元。
編號 4 的車輛停入 3 號停車位 (最後一個空位)，並且付 800*5 = 4000 元。

Sample #2:
編號 3 的車輛停入 1 號停車位，並且付 1000*5 = 5000 元。
編號 1 的車輛停入 2 號停車位，並且付 100*2 = 200 元。
編號 2 的車輛抵達，並且在入口處等待。
編號 4 的車輛抵達，並且在入口處且編號 2 的車輛後方等待。
當編號 1 的車輛離開後，編號 2 的車輛停入停車位，並且付 500*2 = 1000 元。
當編號 3 的車輛離開後，編號 4 的車輛停入停車位，並且付 2000*5 = 10000 元。

Source:

IOI 2009

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	32767kb
0-2	1000ms	32767kb
1	1000ms	32767kb	5
2	1000ms	32767kb	5
3	1000ms	32767kb	5
4	1000ms	32767kb	5
5	1000ms	32767kb	5
6	1000ms	32767kb	5
7	1000ms	32767kb	5
8	1000ms	32767kb	5
9	1000ms	32767kb	5
10	1000ms	32767kb	5
11	1000ms	32767kb	5
12	1000ms	32767kb	5
13	1000ms	32767kb	5
14	1000ms	32767kb	5
15	1000ms	32767kb	5
16	1000ms	32767kb	5
17	1000ms	32767kb	5
18	1000ms	32767kb	5
19	1000ms	32767kb	5
20	1000ms	32767kb	5