题目描述

本题故事由大语言模型生成。如有雷同，纯属巧合。

你刚加入一家知名自研 AI 公司。表面上风光无限，其实你知道：你的工作其实是反向工程了竞争对手的模型，拼拼凑凑后贴上了自家 Logo 就发布了。

模型能用是能用...但非常卡。CTO 怒不可遏，要你马上优化到不卡。

这个模型由 $n$ 个紧密耦合的组件构成（都是借鉴的，所以你的团队里没人会优化）。这些组件之间存在计算依赖关系，构成一个有向无环图。每个组件在其所有依赖组件完成后才能开始计算。

第 $i$ 个组件需要 $w_i$ 毫秒来完成计算。一旦开始计算，它会在恰好 $w_i$ 毫秒后结束。

为了提速，你的任务是把计算过程划分成若干批：在任何时刻，只要满足依赖条件，你都可以并行执行任意可用组件的非空子集。其中，可用组件是指在所有前置组件计算完成的组件。

在每一批中，所有被选中的组件必须一起执行完，才能进行下一批的计算。因此，每个批次的执行时长由其中最慢的组件决定。

你的目标是安排整个执行过程，使得所有依赖条件都被满足，并使总耗时（即所有批的耗时之和）最小。

输入格式

第一行包含两个整数 $n$ 和 $m$ （$1 ≤ n ≤ 24, 0 ≤ m ≤ \binom{n}{2}$），表示组件数量以及依赖关系的数量。

第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$ （1 ≤ $w_i \leq 10^6$ ），表示每个组件的执行时间。

接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$ （$1 ≤ u, v \leq n, u \neq v$ ），表示组件 $v$ 的计算依赖于组件 $u$。换句话说，必须先完成 $u$，才能开始 $v$。

保证依赖图是有向无环图，且不存在重复边。

输出格式

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

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

12

3 1
1 4 5
1 3

5

解释 #1、2