题目内容

设计一个调度系统管理昇腾 $NPU$ 上的训练任务，需满足以下条件：

任务属性（每个任务包含$3$个维度）

1. $npus$：所需 $NPU$ 卡编号列表
2. $duration$：执行需要的时间片数
3. $depend_on$：必须在该任务前完成的任务 $ID$（只会依赖 $0$ 或者 $1$ 个上游任务）

调度规则

1. 每张 $NPU$ 卡同一时间只能执行一个任务
2. 任务必须在前置任务完成后才能开始
3. 时间片为正整数，多个满足条件的任务可并行启动，不可抢占已分配任务
4. 可能存在多种调度方案，需要选出全部任务结束耗时最短的一种

用例保证存在可调度方案（不存在任务间循环依赖），输出所有任务全部完成需要的最短时间。

输入描述

第 $1$ 行，$NPU$ 卡总数（$1<=NPU卡总数<=10$），总任务数量（$1<=总任务数量<=8$），如：$4$ $2$

第 $2$ 行，【第 $2-4$ 行第 $0$ 个任务】，任务 $0$ 依赖的 $npu$ 列表（空格分割），如：$0$ $1$

第 $3$ 行，【第 $2-4$ 行第 $0$ 个任务】，任务 $0$ 持续时间，如：$5$

第 $4$ 行，【第 $2-4$ 行第 $0$ 个任务】，任务 $0$ 依赖的上游任务 $ID$（无依赖时固定为 $-1$），如：$1$

第 $5$ 行，【第 $5-7$ 行第 $1$ 个任务】，任务 $1$ 依赖的 $npu$ 列表（空格分割），如：$1$ $2$

第 $6$ 行，【第 $5-7$ 行第 $1$ 个任务】，任务 $1$ 持续时间，如：$4$

第 $7$ 行，【第 $5-7$ 行第 $1$ 个任务】，任务 $1$ 依赖的上游任务 $ID$（无依赖时固定为 $-1$），如：$0$

……，如果存在更多任务，$3$ 行一组进行输入，任务 $i$ 依赖的 $npu$ 列表（空格分割），如：$1$ $2$

……，如果存在更多任务，$3$ 行一组进行输入，任务 $i$ 持续时间，如：$4$

……，如果存在更多任务，$3$ 行一组进行输入，任务 $i$ 依赖的上游任务 $ID$（无依赖时固定为 $-1$），如：$0$

注意：题目保证输入合法，无需校验输入

输出描述

格式：$int$ 类型数值

解释：所有任务全部完成需要的最短时间，用例保证存在可调度方案（不存在任务间循环依赖）

样例1

输入

2 3
0
3
-1
0
2
-1
1
4
1

输出

6

说明

• $2$ # $2$个NPU卡，$3$个任务
• $0$ # 任务$0$需要NPU卡$0$
• $3$ # 任务$0$持续$3$
• $-1$ # 任务$0$无依赖
• $0$ # 任务$1$需要NPU卡$0$
• $2$ # 任务$1$持续$2$
• $-1$ # 任务$1$无依赖
• $1$ # 任务$2$需要NPU卡$1$
• $4$ # 任务$2$持续$4$
• $1$ # 任务$2$依赖任务$1$

方案1：优先执行耗时长的任务（任务$0$先执行）

• 时间$0$~$3$ NPU$0$: 任务$0$（持续$3$，时间$0$-$3$） NPU$1$: 空闲（任务$2$依赖任务$1$，还未完成）

• 时间$3$~$5$ NPU$0$: 任务$1$（持续$2$，时间$3$-$5$） NPU$1$: 空闲（任务$2$需等待任务$1$，任务$1$在时间$5$完成，但任务$2$还未开始）

• 时间$5$~$9$ NPU$0$: 空闲 NPU$1$: 任务$2$（持续$4$，时间$5$-$9$）

任务完成时间： 任务$0$: 时间$3$完成 任务$1$: 时间$5$完成 任务$2$: 时间$9$完成

总时间：$9$

方案2：优先执行耗时短的任务（任务$1$先执行）

• 时间$0$~$2$ NPU$0$: 任务$1$（持续$2$，时间$0$-$2$） NPU$1$: 空闲（任务$2$依赖任务$1$，还未完成）

• 时间$2$~$6$ NPU$0$: 任务$0$（持续$3$，时间$2$-$5$） NPU$1$: 任务$2$（持续$4$，时间$2$-$6$，任务$1$在时间$2$已完成，满足依赖）

• 时间$5$~$6$ NPU$0$: 空闲（任务$0$已完成） NPU$1$: 任务$2$继续执行（时间$5$-$6$）

任务完成时间：

任务$1$: 时间$2$完成 任务$0$: 时间$5$完成 任务$2$: 时间$6$完成

总时间：$6$

样例2

输入

3 2
0 1
4
-1
1 2
5
0

输出

9

说明

• $3$ $2$ # $3$个NPU卡，$2$个任务
• $0\ 1$ # 任务$0$需要NPU卡$0$、卡$1$
• $4$ # 任务$0$持续$4$
• $-1$ # 任务$0$无依赖
• $1\ 2$ # 任务$1$需要NPU卡$1$、卡$2$
• $5$ # 任务$1$持续$5$
• $0$ # 任务$1$依赖任务$0$

调度顺序： 任务$1$依赖任务$0$，只能先执行任务$0$再执行任务$1$，总耗时$4+5=9$，输出$9$

提示 $NPU$ 编号从 $0$ 开始，任务编号从 $O$ 开始