A171747.Yuilice 的共用设备

Yuilice 有 $n$ 个任务需要在共用设备上执行。任务编号为 $1$ 到 $n$，第 $i$ 个任务需要 $t_i$ 个时间单位。

设备可以分批执行任务，每一批同时执行 $1$ 到 $3$ 个任务。同一批中的任务同时开始，这一批的耗时等于其中最长任务的耗时。只有当前批次全部完成，下一批才能开始。

有 $m$ 对任务存在冲突，每对冲突任务不能放在同一批。冲突关系是双向的，批内任意两任务都不能冲突。

每个任务必须执行恰好一次，各批的先后顺序不限。请计算完成全部任务的最短总时间。

第一行包含两个整数 $n,m$，分别表示任务数量和存在冲突的任务对数量。

第二行包含 $n$ 个整数 $t_1,\ldots,t_n$，其中 $t_i$ 表示第 $i$ 个任务所需的执行时间。

接下来 $m$ 行，每行包含两个整数 $u,v$，分别表示一对冲突任务的编号，这两个任务不能放在同一批。保证 $u\ne v$，每个无序任务对最多出现一次。

输出一个整数，表示完成全部任务的最短总时间。

样例解释

样例 $1$：将任务 $1,3$ 分为一批，任务 $2,4$ 分为另一批，总时间为 $1+1=2$。每批至多三个任务，四个任务至少需要两批，所以该方案最优。若先把任务 $1,2$ 放在同一批，剩下的任务 $3,4$ 互相冲突，需要各自一批。

样例 $2$：将耗时为 $9,8,7$ 的任务分为一批，剩余两任务为另一批，总时间为 $9+6=15$。

数据范围

对于所有测试数据，满足 $1\le n\le18$，$0\le m\le n(n-1)/2$，$1\le t_i\le10^9$，$1\le u,v\le n$。

测试点	分值	额外限制
1–2	10	$m=0$
3–6	20	$n\le9$
7–20	70	无额外限制