解题思路

这道题本质上是一个：

• 带依赖约束的任务调度问题
• 有且仅有 $2$ 个线程（两台相同机器）
• 每个任务一旦开始编译就不能中断
• 目标是最小化所有任务完成的总时间

题目内容

代码工程编译时，需要编译所有的 $Target$ 完成整个工程的编译，但是 $Target$ 之间往往存在单向的依赖关系，当前 $Target$ 依赖的所有 $Target$ 完成编译后才能正常编译，并且在一个线程上编译一个 $Target$ 时无法暂停或者中断。 只能等待其编译完成，之后才能在该线程上继续编译其它 $Target$。

为了加快编译速度，$IDE$ 会利用 $CPU$ 多线程并行特性，并行调度编译编译这些 $Target$。

现在有个工程有 $N$ 个 $Target$，你有一个双线程的 $CPU$ 可用于编译，你能帮忙安排一个编译调度方案以最快的速度完成工程的编译，并计算出最短的耗时吗？

输入描述

第一行输入 $N（1 ≤ N ≤ 10），K（0 ≤ K ≤ 50）$，表示有 $N$ 个 $Target$ 需要编译，有 $K$ 个依赖关系。

接下来 $N$ 行，每行输入一个数字 $Wi（1 ≤ Wi ≤ 100）$，表示第 $i$ 个 $Target$ 编译需要耗费的时间。

接下来 $K$ 行，每行输入 $i, j（1 ≤ i, j ≤ N,$ 且 $i$ $!$ $≠ j）$，表示第 $i$ 个 $Target$ 依赖第 $j$ 个 $Target$。

输出描述

输出一行一个数字 $T$，表示最快完成工程编译的时间，如果无法完成工程编译，则输出 $-1$。

补充说明

本题所有的输入数据均为整数。

样例1

输入

3 2
4
3
2
1 2
2 3

输出

9

说明

由于 $1->2->3$ 存在链式依赖，无法并行，所以完全串行编译需要 $9$ 单位时间。

样例2

输入

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

输出

10

说明

编译开始时只有第 $4$ 个 $Target$ 无依赖，所以消耗 $2$ 单位时间进行编译。

之后第 $2、3$ 个 $Target$ 可并行编译，消耗 $3$ 时间单位。

最后编译剩下的第 $1$ 个 $Target$，消耗 $5$ 单位时间。

整个编译流程总消耗 $10$ 单位时间。

样例3

输入

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

输出

-1

说明

$Target$ 之间存在 $2->3->4->2$ 的循环依赖关系，所以会编译失败，输出 $-1$。