分数: 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