Một bãi đỗ xe có \(N\) chỗ đỗ, được đánh số từ \(1\) đến \(N\). Mỗi sáng, khi mở cửa, bãi chưa có xe nào và hoạt động trong ngày theo quy tắc sau. Mỗi khi một xe đến, nhân viên kiểm tra xem còn chỗ trống hay không. Nếu không còn, xe phải chờ ở lối vào cho đến khi có một chỗ được giải phóng. Nếu có chỗ trống, hoặc ngay khi có một chỗ trở nên trống, xe được đưa vào chỗ đó. Nếu có nhiều chỗ trống, xe được đưa vào chỗ có số hiệu nhỏ nhất. Nếu có thêm xe đến trong khi đã có xe đang chờ, các xe xếp thành một hàng ở lối vào theo thứ tự đến. Khi có chỗ trống, xe ở đầu hàng, tức là xe đến sớm nhất trong số các xe đang chờ, được đưa vào chỗ đó.

Phí đỗ xe, tính bằng đô la, bằng khối lượng của xe tính bằng kilôgam nhân với đơn giá của chỗ đỗ mà xe sử dụng. Phí không phụ thuộc vào thời gian xe ở trong bãi.

Người quản lý biết hôm nay sẽ có \(M\) xe đến và biết thứ tự các xe đến và rời bãi. Hãy giúp người đó tính tổng doanh thu trong ngày, tính bằng đô la.

Cho đơn giá của các chỗ đỗ, khối lượng các xe và thứ tự các xe đến và rời bãi, hãy viết chương trình xác định tổng doanh thu của bãi đỗ xe.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N\) và \(M\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo mô tả đơn giá của các chỗ đỗ. Dòng thứ \(s\) trong số này chứa một số nguyên \(R_s\), là đơn giá của chỗ đỗ số \(s\), tính bằng đô la trên kilôgam.
• \(M\) dòng tiếp theo mô tả khối lượng của các xe. Các xe được đánh số từ \(1\) đến \(M\) theo thứ tự tùy ý. Dòng thứ \(k\) trong số này chứa một số nguyên \(W_k\), là khối lượng của xe số \(k\), tính bằng kilôgam.
• \(2M\) dòng tiếp theo mô tả các lần đến và rời bãi của tất cả các xe theo thứ tự thời gian. Mỗi dòng chứa một số nguyên: số dương \(i\) cho biết xe số \(i\) đến bãi; số âm \(-i\) cho biết xe số \(i\) rời bãi. Không xe nào rời bãi trước khi đến. Mỗi xe từ \(1\) đến \(M\) xuất hiện đúng hai lần trong dãy này, một lần đến và một lần rời bãi. Hơn nữa, không xe nào rời bãi trước khi đã được đỗ vào một chỗ, tức là không xe nào bỏ đi khi vẫn đang chờ trong hàng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: tổng số đô la mà người quản lý bãi đỗ xe thu được trong ngày hôm nay.

Ràng buộc

• \(1 \le N \le 100\): số chỗ đỗ xe.
• \(1 \le M \le 2\,000\): số xe.
• \(1 \le R_s \le 100\) với \(1 \le s \le N\): đơn giá của chỗ đỗ số \(s\), tính bằng đô la trên kilôgam.
• \(1 \le W_k \le 10\,000\) với \(1 \le k \le M\): khối lượng xe số \(k\), tính bằng kilôgam.

Phân nhóm

Một số bộ dữ liệu có tổng cộng \(40\) điểm bảo đảm rằng mỗi khi một xe đến, luôn có ít nhất một chỗ đỗ còn trống. Trong các bộ dữ liệu này, không xe nào phải chờ chỗ đỗ.

Ví dụ

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

Nguồn

IOI 2009, ngày thi thứ hai: Garage, bản tiếng Anh 1.2. Tác giả đề bài: Carl Hultquist. Tập đề bài và lời giải IOI 2009.