A - Budget and Estimate Discrepancy Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は、会社の備品購入を担当しています。会社では N 種類の備品を取り扱っており、備品には 1 から N までの番号が付けられています。備品 i の実際の価格は P_i 円です。

ある日、高橋君が使用している古い価格表に誤りがあることが判明しました。この古い価格表では、備品 i の価格が Q_i 円と記載されています。

高橋君は、各部署からの購入申請に対して、実際の購入金額と古い価格表に基づく見積もり金額との差額を報告する必要があります。

今日、M 個の部署から購入申請がありました。j 番目の部署は、K_j 種類の備品を各 1 個ずつ購入することを希望しており、購入を希望する備品の番号は C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} です。同じ部署の購入希望リストに同一の備品番号が複数回現れることはありません。

各部署について、実際の合計金額から古い価格表に基づく見積もり合計金額を引いた値、すなわち

\sum_{k=1}^{K_j} (P_{C_{j,k}} - Q_{C_{j,k}})

を求めてください。この値は負になることもあります。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq Q_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq K_j \leq N (1 \leq j \leq M)
  • 1 \leq C_{j,k} \leq N (1 \leq j \leq M, 1 \leq k \leq K_j)
  • C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} は互いに異なる (1 \leq j \leq M)
  • \sum_{j=1}^{M} K_j \leq 2 \times 10^5
  • 入力はすべて整数

入力

N M
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N
K_1 C_{1,1} C_{1,2} \ldots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \ldots C_{2,K_2}
\vdots
K_M C_{M,1} C_{M,2} \ldots C_{M,K_M}
  • 1 行目には、備品の種類数 N と部署の数 M が、スペース区切りで与えられる。
  • 2 行目には、各備品の実際の価格 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
  • 3 行目には、古い価格表に記載されている各備品の価格 Q_1, Q_2, \ldots, Q_N が、スペース区切りで与えられる。
  • 4 行目から 3+M 行目まで、各部署の購入申請情報が与えられる。第 3 + j 行目には、j 番目の部署が購入を希望する備品の種類数 K_j と、購入を希望する備品の番号 C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} が、スペース区切りで与えられる。

出力

M 行にわたって出力せよ。j 行目 (1 \leq j \leq M) には、j 番目の部署について、実際の合計金額から古い価格表に基づく見積もり合計金額を引いた値を整数で出力せよ。

入力例 1

3 2
100 200 300
90 250 280
2 1 3
3 1 2 3

出力例 1

30
-20

入力例 2

4 3
50 30 100 200
100 80 50 300
1 1
2 3 4
4 1 2 3 4

出力例 2

-50
-50
-150

入力例 3

8 5
500 1200 800 350 960 1500 2200 430
480 1300 750 400 1000 1450 2100 500
3 1 4 7
2 2 6
5 1 2 3 4 5
1 8
4 5 6 7 8

出力例 3

70
-50
-120
-70
40

入力例 4

10 8
1000000000 999999999 500000000 123456789 777777777 100 200 300 999999 1
900000000 1000000000 600000000 123456790 777777776 200 100 400 999998 2
3 1 2 3
4 4 5 6 7
2 8 9
1 10
5 1 3 5 7 10
10 1 2 3 4 5 6 7 8 9 10
2 1 10
3 6 7 8

出力例 4

-1
0
-99
-1
100
-101
99999999
-100

入力例 5

1 1
1000000000
1
1 1

出力例 5

999999999

Score : 233 pts

Problem Statement

Takahashi is in charge of purchasing supplies for his company. The company handles N types of supplies, numbered from 1 to N. The actual price of supply i is P_i yen.

One day, it was discovered that the old price list Takahashi had been using contained errors. In this old price list, the price of supply i is listed as Q_i yen.

Takahashi needs to report the difference between the actual purchase amount and the estimated amount based on the old price list for each department's purchase request.

Today, purchase requests were received from M departments. The j-th department wishes to purchase K_j types of supplies, one of each, and the supply numbers they wish to purchase are C_{j,1}, C_{j,2}, \ldots, C_{j,K_j}. The same supply number does not appear more than once in the same department's purchase request list.

For each department, find the value obtained by subtracting the estimated total amount based on the old price list from the actual total amount, that is:

\sum_{k=1}^{K_j} (P_{C_{j,k}} - Q_{C_{j,k}})

This value may be negative.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq Q_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq K_j \leq N (1 \leq j \leq M)
  • 1 \leq C_{j,k} \leq N (1 \leq j \leq M, 1 \leq k \leq K_j)
  • C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} are pairwise distinct (1 \leq j \leq M)
  • \sum_{j=1}^{M} K_j \leq 2 \times 10^5
  • All inputs are integers

Input

N M
P_1 P_2 \ldots P_N
Q_1 Q_2 \ldots Q_N
K_1 C_{1,1} C_{1,2} \ldots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \ldots C_{2,K_2}
\vdots
K_M C_{M,1} C_{M,2} \ldots C_{M,K_M}
  • The first line contains the number of supply types N and the number of departments M, separated by a space.
  • The second line contains the actual prices of each supply P_1, P_2, \ldots, P_N, separated by spaces.
  • The third line contains the prices listed in the old price list for each supply Q_1, Q_2, \ldots, Q_N, separated by spaces.
  • From the 4th line to the (3+M)-th line, the purchase request information for each department is given. The (3 + j)-th line contains the number of supply types K_j that the j-th department wishes to purchase, followed by the supply numbers C_{j,1}, C_{j,2}, \ldots, C_{j,K_j} they wish to purchase, separated by spaces.

Output

Output M lines. On the j-th line (1 \leq j \leq M), output as an integer the value obtained by subtracting the estimated total amount based on the old price list from the actual total amount for the j-th department.

Sample Input 1

3 2
100 200 300
90 250 280
2 1 3
3 1 2 3

Sample Output 1

30
-20

Sample Input 2

4 3
50 30 100 200
100 80 50 300
1 1
2 3 4
4 1 2 3 4

Sample Output 2

-50
-50
-150

Sample Input 3

8 5
500 1200 800 350 960 1500 2200 430
480 1300 750 400 1000 1450 2100 500
3 1 4 7
2 2 6
5 1 2 3 4 5
1 8
4 5 6 7 8

Sample Output 3

70
-50
-120
-70
40

Sample Input 4

10 8
1000000000 999999999 500000000 123456789 777777777 100 200 300 999999 1
900000000 1000000000 600000000 123456790 777777776 200 100 400 999998 2
3 1 2 3
4 4 5 6 7
2 8 9
1 10
5 1 3 5 7 10
10 1 2 3 4 5 6 7 8 9 10
2 1 10
3 6 7 8

Sample Output 4

-1
0
-99
-1
100
-101
99999999
-100

Sample Input 5

1 1
1000000000
1
1 1

Sample Output 5

999999999