A - お弁当の注文 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君はお弁当屋さんで働いています。お店では N 種類のおかずを取り扱っており、おかずには 1 から N までの番号が付いています。おかず i の価格は W_i 円です。

今日は M 件の注文が入っています。 j 件目の注文では K_j 種類のおかずが選ばれており、具体的にはおかず A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j} が選ばれています。同じ注文の中で同じおかずが複数回選ばれることはありません。

各注文について、選ばれたおかずの合計金額を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq W_i \leq 10^4 (1 \leq i \leq N)
  • 1 \leq K_j \leq N (1 \leq j \leq M)
  • 1 \leq A_{j, k} \leq N (1 \leq j \leq M,\ 1 \leq k \leq K_j)
  • j 件目の注文において、A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j} はすべて異なる
  • \displaystyle \sum_{j=1}^{M} K_j \leq 10^6
  • 入力はすべて整数である

入力

入力は以下の形式で与えられる。

N M
W_1 W_2 \dots W_N
K_1 A_{1, 1} A_{1, 2} \dots A_{1, K_1}
K_2 A_{2, 1} A_{2, 2} \dots A_{2, K_2}
\vdots
K_M A_{M, 1} A_{M, 2} \dots A_{M, K_M}
  • 1 行目には、おかずの種類数 N と注文の件数 M がスペース区切りで与えられる。
  • 2 行目には、各おかずの価格を表す N 個の整数 W_1, W_2, \dots, W_N がスペース区切りで与えられる。
  • 続く M 行にわたって、各注文で選ばれたおかずの情報が与えられる。
  • 2 + j 行目には、 j 件目の注文で選ばれたおかずの数 K_j と、選ばれたおかずの番号を表す K_j 個の整数 A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j} がスペース区切りで与えられる。

出力

出力は M 行からなる。

j 行目には、 j 件目の注文で選ばれたおかずの合計金額を出力せよ。

入力例 1

4 3
300 500 120 450
2 1 3
3 2 4 1
1 2

出力例 1

420
1250
500

入力例 2

5 4
1000 250 400 800 150
5 1 2 3 4 5
2 5 2
3 3 1 4
1 4

出力例 2

2600
400
2200
800

入力例 3

9 6
130 260 390 520 150 280 410 540 170
4 1 3 5 7
3 9 2 4
5 8 6 4 2 1
2 5 9
6 3 4 5 6 7 8
1 2

出力例 3

1080
950
1730
320
2290
260

入力例 4

20 10
95 180 260 340 420 510 605 715 830 940 55 165 275 385 495 610 720 845 960 1000
5 1 5 10 15 20
8 2 4 6 8 12 14 16 18
10 1 2 3 4 5 6 7 8 9 10
7 11 12 13 14 15 16 17
3 19 20 1
12 20 18 16 14 12 10 8 6 4 2 1 3
1 11
9 5 7 9 11 13 15 17 19 20
4 3 6 9 12
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

出力例 4

2950
3750
4895
2705
2055
6045
55
5360
1765
10405

入力例 5

1 1
9999
1 1

出力例 5

9999

Score : 233 pts

Problem Statement

Takahashi works at a bento (lunch box) shop. The shop offers N types of side dishes, numbered from 1 to N. The price of side dish i is W_i yen.

Today, there are M orders. The j-th order has K_j types of side dishes selected, specifically side dishes A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j}. The same side dish is never selected more than once within the same order.

For each order, calculate the total price of the selected side dishes.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq W_i \leq 10^4 (1 \leq i \leq N)
  • 1 \leq K_j \leq N (1 \leq j \leq M)
  • 1 \leq A_{j, k} \leq N (1 \leq j \leq M,\ 1 \leq k \leq K_j)
  • In the j-th order, A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j} are all distinct
  • \displaystyle \sum_{j=1}^{M} K_j \leq 10^6
  • All input values are integers

Input

The input is given in the following format.

N M
W_1 W_2 \dots W_N
K_1 A_{1, 1} A_{1, 2} \dots A_{1, K_1}
K_2 A_{2, 1} A_{2, 2} \dots A_{2, K_2}
\vdots
K_M A_{M, 1} A_{M, 2} \dots A_{M, K_M}
  • The first line contains the number of side dish types N and the number of orders M, separated by a space.
  • The second line contains N integers W_1, W_2, \dots, W_N representing the price of each side dish, separated by spaces.
  • The following M lines contain the information about the side dishes selected in each order.
  • The (2 + j)-th line contains the number of side dishes selected in the j-th order K_j, followed by K_j integers A_{j, 1}, A_{j, 2}, \dots, A_{j, K_j} representing the numbers of the selected side dishes, separated by spaces.

Output

The output consists of M lines.

On the j-th line, output the total price of the side dishes selected in the j-th order.

Sample Input 1

4 3
300 500 120 450
2 1 3
3 2 4 1
1 2

Sample Output 1

420
1250
500

Sample Input 2

5 4
1000 250 400 800 150
5 1 2 3 4 5
2 5 2
3 3 1 4
1 4

Sample Output 2

2600
400
2200
800

Sample Input 3

9 6
130 260 390 520 150 280 410 540 170
4 1 3 5 7
3 9 2 4
5 8 6 4 2 1
2 5 9
6 3 4 5 6 7 8
1 2

Sample Output 3

1080
950
1730
320
2290
260

Sample Input 4

20 10
95 180 260 340 420 510 605 715 830 940 55 165 275 385 495 610 720 845 960 1000
5 1 5 10 15 20
8 2 4 6 8 12 14 16 18
10 1 2 3 4 5 6 7 8 9 10
7 11 12 13 14 15 16 17
3 19 20 1
12 20 18 16 14 12 10 8 6 4 2 1 3
1 11
9 5 7 9 11 13 15 17 19 20
4 3 6 9 12
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Sample Output 4

2950
3750
4895
2705
2055
6045
55
5360
1765
10405

Sample Input 5

1 1
9999
1 1

Sample Output 5

9999