9779: 开天辟地

内存限制:1024 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:3 通过:1

题目描述

本题故事由大语言模型生成。如有雷同,纯属巧合。
你刚加入一家知名自研 AI 公司。表面上风光无限,其实你知道:你的工作其实是反向工程了竞争对手
的模型,拼拼凑凑后贴上了自家 Logo 就发布了。
模型能用是能用. . . 但非非非常常常卡卡卡。CTO 怒不可遏,要你马上优化到不卡。
这个模型由 n 个紧密耦合的组件构成(都是借鉴的,所以你的团队里没人会优化)。这些组件之间存在
计算依赖关系,构成一个有向无环图。每个组件在其所有依赖组件完成后才能开始计算。
第 i 个组件需要 wi 毫秒来完成计算。一旦开始计算,它会在恰好 wi 毫秒后结束。
为了提速,你的任务是把计算过程划分成若干批:在任何时刻,只要满足依赖条件,你都可以并行执行
任意可用组件的非空子集。其中,可用组件是指在所有前置组件计算完成的组件。
在每一批中,所有被选中的组件必须一起执行完,才能进行下一批的计算。因此,每个批次的执行时长
由其中最慢的组件决定。
你的目标是安排整个执行过程,使得所有依赖条件都被满足,并使总耗时(即所有批的耗时之和)最
小。

输入格式

第一行包含两个整数 n 和 m(1 ≤ n ≤ 24, 0 ≤ m ≤ n*(n-1)/2,表示组件数量以及依赖关系的数量。
第二行包含 n 个整数 w1, w2, . . . , wn(1 ≤ wi ≤ 106),表示每个组件的执行时间。
接下来的 m 行中,每行包含两个整数 u 和 v(1 ≤ u, v ≤ n, u 不等于 v),表示组件 v 的计算依赖于组件u。换句话说,必须先完成 u,才能开始 v。
保证依赖图是有向无环图,且不存在重复边。

输出格式

输出一个整数,表示最小可能的批次延迟总和。

输入样例#1 复制

5 4
3 1 4 1 5
1 3
2 3
3 4
3 5

输出样例#1 复制

12

输入样例#2 复制

3 1
1 4 5
1 3

输出样例#2 复制

6