分数: 400 分
问题陈述
高桥负责举办公司演讲比赛。在本次比赛中, N 员工将进行演示,每个员工都会被分配一个编号 1 to N.
每位员工 i (1 \leq i \leq N) 有一个正整数 A_i 代表他们的“演讲技巧”。
比赛中,各 N 为员工分配了唯一的演示顺序 1st 至 N第。让 P_i 表示员工所在的职位 i 呈现。然后 (P_1, P_2, \ldots, P_N) 是一个排列 (1, 2, \ldots, N)。演讲按顺序进行: 1圣, 2nd, \ldots, N第。
员工的“贡献” i 定义为 A_i \times P_i。竞赛的“总分”定义为所有员工贡献的总和:
\displaystyle\sum_{i=1}^{N} A_i \times P_i
高桥想要最大化总分。然而,青木强加了 M 限制。每个约束 k (1 \leq k \leq M) 指出“员工 U_k 必须在员工面前出现 V_k (即 P_{U_k} < P_{V_k})".
在满足所有约束的所有呈现顺序中,找到总分最大的一个,并输出最大总分。
保证存在至少一个满足所有约束的呈现顺序。
约束
- 1 \leq N \leq 8
- 0 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq A_i \leq 100 (1 \leq i \leq N)
- 1 \leq U_k, V_k \leq N (1 \leq k \leq M)
- U_k \neq V_k (1 \leq k \leq M)
- 同一对 (U_k, V_k) 未给出多次。
- 至少存在一种满足所有约束的呈现顺序(即,以员工为顶点、约束为有向边的有向图是 DAG)。
- 所有输入值均为整数。
输入
N M A_1 A_2 \ldots A_N U_1 V_1 U_2 V_2 \vdots U_M V_M
- 第一行包含 N,员工人数,以及 M,约束数量,以空格分隔。
- 第二行包含 A_1, A_2, \ldots, A_N,每个员工的演示技巧,以空格分隔。
- 以下 M 行包含约束。当以下情况时这些行不存在 M = 0.
- 的 (2 + k)第行 (1 \leq k \leq M) 包含 U_k 和 V_k,以空格分隔,表示员工 U_k 必须在员工面前出现 V_k.
输出
在单行中输出满足所有约束的所有呈现顺序中的最大总分。
示例输入 1
3 1 1 2 3 1 2
示例输出 1
14
示例输入 2
3 1 3 1 2 1 3
示例输出 2
13
示例输入 3
5 3 5 3 8 1 6 4 1 4 2 3 5
示例输出 3
84
示例输入 4
8 4 10 20 30 40 50 60 70 80 1 2 3 4 5 6 7 8
示例输出 4
2040
示例输入 5
1 0 42
示例输出 5
42