Public Judge

pjudge

Time Limit: 3 s Memory Limit: 512 MB Total points: 100 Hackable ✓

# 21703. 【NOIP Round #4】治病

统计

题目描述

虱子国王尼特这天有点不舒服,它周围的 $n$ 个医生立刻开出了药方:第 $i$ 个医生告诉它,从这天起的第 $L_i$ 天到第 $R_i$ 天,它应该服用 $x_{i,1},x_{i,2},\dots,x_{i,K_i}$ 这 $K_i$ 种药,每天每种药应当服用恰好一片。注意,如果有多个医生的药方里都要求尼特在第 $p$ 天服用第 $q$ 种药,那尼特在第 $p$ 天仍然只会服用一片第 $q$ 种药。编号为 $j$ 的药每片需要 $c_j$ 元钱。

然而,由于尼特的疏忽,有恰好一位庸医混进了医生队伍里,但尼特并不知道哪位医生是庸医。所以它想知道,对于所有 $1\le i\le n$,如果它按照除了第 $i$ 个医生之外的所有医生的药方吃药,它总共将花费多少钱。

输入格式

第一行两个正整数 $n,m$,分别为医生数和药片种类数。

接下来一行 $m$ 个正整数 $c_1\sim c_m$。

接下来 $n$ 行,第 $i$ 行描述第 $i$ 个医生。首先三个正整数 $L_i,R_i,K_i$,后面 $K_i$ 个正整数 $x_{i,1},x_{i,2},\dots,x_{i,K_i}$。保证 $x_{i,1},x_{i,2},\dots,x_{i,K_i}$ 互不相同。

输出格式

输出 $n$ 个非负整数,第 $i$ 个表示,如果尼特认为第 $i$ 个医生是庸医并除开他的药方,它总共将花费多少钱。

样例输入输出

样例输入 1

5 4
10000 1000 100 10
3 4 2 2 3
4 8 3 1 2 4
6 7 2 3 4
8 9 2 1 4
2 6 3 1 2 3

样例输出 1

87660 75640 87560 77650 66460

样例 1 解释

这里仅解释输出中的第一个和第五个数。

如果第一位医生是庸医,则尼特:

  • 在第 $2,3$ 天会吃药片 $1,2,3$。花费 $11100\times 2=22200$ 元。
  • 在第 $4,5,6,7$ 天会吃药片 $1,2,3,4$。花费 $11110\times 4=44440$ 元。
  • 在第 $8$ 天会吃药片 $1,2,4$。花费 $11010$ 元。
  • 在第 $9$ 天会吃药片 $1,4$。花费 $10010$ 元。

总花费 $87660$ 元。

如果第五位医生是庸医,则尼特:

  • 在第 $3$ 天会吃药片 $2,3$。花费 $1100$ 元。
  • 在第 $4$ 天会吃药片 $1,2,3,4$。花费 $11110$ 元。
  • 在第 $5$ 天会吃药片 $1,2,4$。花费 $11010$ 元。
  • 在第 $6,7$ 天会吃药片 $1,2,3,4$。花费 $11110\times 2=22220$ 元。
  • 在第 $8$ 天会吃药片 $1,2,4$。花费 $11010$ 元。
  • 在第 $9$ 天会吃药片 $1,4$。花费 $10010$ 元。

总花费 $66460$ 元。

样例 2/3/4

见下发文件。

样例 $2$ 满足子任务 $1$ 的限制。

样例 $3$ 满足子任务 $3$ 的限制。

样例 $4$ 满足子任务 $5$ 的限制。

数据范围

本题捆绑测试。对于所有数据:$1\le n,m\le 5\times 10^5,1\le L_i\le R_i\le 10^6,1\le K_i\le m,\sum K_i\le 10^6, 1 \leq c_i \leq 10^6$。

子任务编号 特殊性质 分数
$1$ $n\le 100,m\le 100,R_i\le 100,\sum K_i\le 100$ $20$
$2$ $n\le 5000,m\le 5000,R_i\le 5000,\sum K_i\le 10^4$ $20$
$3$ $[L_i,R_i]$ 互不相交 $20$
$4$ $m=1$ $20$
$5$ $20$

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$