题目内容

某校有 $n$ 篇论文需要分配给教师评审。

• 每篇论文 $i$ 可由文件 files[i] 对应的教师列表中任一教师评审。
• 每篇论文至少需要一名教师评审。
• 每位教师 $t$，不论被分配多少篇论文，其评审费用固定为 cost[t]。

请给出参与评审教师数量最少时的总费用；若存在多种方案满足教师数最少，则选择总费用最小的方案。

输入描述

输入，共有 4 个：

• n - 论文篇数

• m - 教师个数

• files - 二维列表，形式为 files[i][j]
  具体内容为：

  • files[0] 允许评审论文 0 的教师列表，列表内有多个数值
  • files[1] 允许评审论文 1 的教师列表
  • ...
  • files[n-1] 允许评审论文 $n-1$ 的教师列表

• cost - 二维列表，列表索引 $t$ 表示教师编号 $t$，列表值表示对应教师编号评审论文的费用

输出描述

返回一个整数，表示参与教师数量最少时的总费用。

约束

• $1 \leq n \leq 20$
• $1 \leq m \leq 12$
• files.length 为 $n$，files[i] 不为空，其中元素满足 $0 \leq files[i][j] < m$
• cost[t] 取值 $> 0$，$0 < t < m$，累计和不超过出整型值范围

样例1

输入

3,3,[[0,1],[1,2],[0,2]],[1,2,2]

输出

3

说明

部分教师可以评审多篇论文：

• $n=3$，$m=3$，files=[[0,1],[1,2],[0,2]]，cost=[1,2,2]，min\_cost=3
• 方案一：编号为 $0$ 和 $2$ 的教师可以完成 $3$ 篇论文评审，编号为 $0$ 和 $2$ 的论文分给教师 $0$，编号为 $1$ 的论文分给 $2$，花费是 $1+2=3$
• 方案二：编号 $1$ 和 $2$ 的也可以完成 $3$ 篇评审，花费是 $2+2=4$
• 所以选择方案一，最小费用是 $3$。

样例2

输入

3,3,[[0],[1],[2]],[1,2,3]

输出

6

说明

• $n=3$，$m=3$，files=[[0],[1],[2]]，每篇论文只有一个教师可选
• cost=[1,2,3]，编号 $0,1,2$ 的教师费用分别为 $1,2,3$
• 每个论文文档只有一个教师可选，所以最小费用是 $6$。

样例3

输入

4,5,[[0,3,4],[1,3],[2,4],[0,4]],[1,1,1,3,3]

输出

4

说明

输入：

• $n=4$，$m=5$
• files=[[0,3,4],[1,3],[2,4],[0,4]]
• cost=[1,1,1,3,3]

覆盖关系：

• 教师 $0 \to$ 论文 $[0,3]$，费用 $1$
• 教师 $1 \to$ 论文 $[1]$，费用 $1$
• 教师 $2 \to$ 论文 $[2]$，费用 $1$
• 教师 $3 \to$ 论文 $[0,1]$，费用 $3$
• 教师 $4 \to$ 论文 $[0,2,3]$，费用 $3$

方案对比：

• $3$ 名教师 $[0,1,2]$ 覆盖全部，费用 $=3$ / 教师多，费用少
• $2$ 名教师 $[1,4]$ 覆盖全部，费用 $=4$ 教师少，费用次优
• $2$ 名教师 $[3,4]$ 覆盖全部，费用 $=6$

输出：$4$

解释：方案 $[0,1,2]$ 用 $3$ 名教师仅花费 $3$，比 $[1,4]$ 的 $4$ 更便宜，但因教师数量为 $3$（多于 $2$）。按“教师最少优先”原则淘汰该法。最终选 $2$ 名教师的方案，在 $[1,4]$ 和 $[3,4]$ 中取费用最小的 $4$。