← 返回题目列表

AtCoder · awc0093_a

A. 盒饭订单

中文机器翻译题面 查看原题

分数: 233 分

问题陈述

高桥在一家便当(午餐盒)店工作。本店提供 N 配菜种类,编号从 1 to N。配菜价格 i is 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}
  • 第一行包含配菜类型的数量 N 和订单数量 M,用空格分隔。
  • 第二行包含 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