小慕正在负责一条水晶炼化流水线的调度工作。每个炼化仪式（任务）需要依赖一些已经存在的水晶，执行完成后又会生成新的水晶。所有仪式通过水晶的依赖关系形成一条完整的炼化流程。 现有一组炼化仪式，记作 `rituals`，其中每个仪式由三个部分组成： * `ritualId`：单个大写字母，表示炼化仪式的标识； * `requiredCrystals[]`：该仪式所依赖的 ID 列表（只有这些水晶都存在时才能启动）； * `producedCrystals[]`：该仪式执行后生成的新水晶 ID 列表。 所有水晶的占用空间记录在数组 `crystalSpace` 中，其中 `crystalSpace[i]` 表示 ID 为 `i` 的水晶所占用的魔法空间大小。 小慕的流水线同一时刻只能执行一个仪式。她需要合理安排所有仪式的执行顺序，使得炼化过程中魔法水晶仓储的最小，并返回这个最小值。 注意： 1. 每个炼化仪式必须执行且仅执行一次； 2. 任意时刻只能执行一个炼化仪式； 3. 一个仪式必须等其所有 `requiredCrystals` 已存在后，才能执行； 4. 水晶一旦被炼化出来就会占用空间，直到时才会立即释放； 5. 仪式执行完毕的流程为： * 先解除对所有前置水晶的依赖； * 再生成自身的新水晶。
提示：带虚线的词点一下有通俗解释。
输入描述
* 第一行包含两个整数 `n` 和 `p`： * `n` 表示炼化仪式的数量 (`1 <= n <= 20`)； * `p` 表示水晶的数量 (`1 <= p <= 100`)。 * 接下来 `n` 行，每行描述一个炼化仪式，格式如下： ``` ritualId k required[0..k-1] m produced[0..m-1] ``` 其中： * `ritualId` 为单个大写字母，表示仪式编号； * `k` 表示该仪式所需的前置水晶数量； * `required[0..k-1]` 表示该仪式所依赖的前置水晶编号； * `m` 表示该仪式生成的新水晶数量； * `produced[0..m-1]` 表示该仪式生成的新水晶编号。 * 最后一行包含 `p` 个整数，表示每个水晶的空间占用大小： * `crystalSpace[i]` 表示编号为 `i` 的水晶所占用的空间 (`10 <= crystalSpace[i] <= 1000`)。
输出描述
输出一个整数，表示最小的峰值魔法空间占用。
示例
示例 1
输入
6 6 A 0 1 5 B 1 5 2 1 3 C 1 1 1 0 D 1 1 1 2 E 3 0 2 3 1 4 F 1 4 0 30 80 20 50 20 50
输出
150
说明：* 仪式 A 首先生成水晶 5； * 仪式 B 使用水晶 5，生成水晶 1、3，5消失； * 仪式 D 使用水晶 1，生成水晶 2； * 仪式 C 使用水晶 1，生成水晶 0，1消失； * 仪式 E 使用水晶 0、2、3，生成水晶 4，0、2、3消失； * 仪式 F 使用水晶 4，流程结束，4消失。 整个流程的最小峰值空间占用为 150。
时间限制 1000 ms · 内存限制 128 MB