D - プレゼンテーションの発表順 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は社内プレゼンテーション大会の司会進行を担当しています。この大会では N 人の社員が発表を行い、それぞれの社員には 1 から N までの番号が付けられています。

各社員 i (1 \leq i \leq N) には「プレゼン力」を表す正の整数 A_i が定められています。

大会では、N 人の社員それぞれに 1 番目から N 番目までの発表順を重複なく割り当てます。社員 i が何番目に発表するかを P_i とすると、(P_1, P_2, \ldots, P_N) は (1, 2, \ldots, N) の順列となります。発表は 1 番目、2 番目、\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 つ存在することが保証されます。

制約

  • 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) の組が複数回与えられることはない。
  • 制約条件を満たす発表順が少なくとも 1 つ存在する（すなわち、社員を頂点、制約条件を有向辺とする有向グラフは DAG である）。
  • 入力はすべて整数である。

入力

N M
A_1 A_2 \ldots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、社員の人数を表す N と、制約条件の数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各社員のプレゼン力を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたり、制約条件が与えられる。M = 0 のときこれらの行は存在しない。
  • 2 + k 行目 (1 \leq k \leq M) には、社員 U_k が社員 V_k よりも先に発表しなければならないことを表す U_k と V_k が、スペース区切りで与えられる。

出力

すべての制約条件を満たす発表順における総合スコアの最大値を 1 行で出力せよ。

入力例 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

Score : 400 pts

Problem Statement

Takahashi is in charge of hosting a company presentation competition. In this competition, N employees will give presentations, and each employee is assigned a number from 1 to N.

Each employee i (1 \leq i \leq N) has a positive integer A_i representing their "presentation skill".

In the competition, each of the N employees is assigned a unique presentation order from 1st to Nth. Let P_i denote the position in which employee i presents. Then (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N). Presentations are given in order: 1st, 2nd, \ldots, Nth.

The "contribution" of employee i is defined as A_i \times P_i. The "total score" of the competition is defined as the sum of contributions of all employees:

\displaystyle\sum_{i=1}^{N} A_i \times P_i

Takahashi wants to maximize the total score. However, Aoki has imposed M constraints. Each constraint k (1 \leq k \leq M) states that "employee U_k must present before employee V_k (i.e., P_{U_k} < P_{V_k})".

Among all presentation orders that satisfy all constraints, find the one that maximizes the total score, and output that maximum total score.

It is guaranteed that at least one presentation order satisfying all constraints exists.

Constraints

  • 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)
  • The same pair (U_k, V_k) is not given more than once.
  • At least one presentation order satisfying all constraints exists (i.e., the directed graph with employees as vertices and constraints as directed edges is a DAG).
  • All input values are integers.

Input

N M
A_1 A_2 \ldots A_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains N, the number of employees, and M, the number of constraints, separated by a space.
  • The second line contains A_1, A_2, \ldots, A_N, the presentation skills of each employee, separated by spaces.
  • The following M lines contain the constraints. These lines do not exist when M = 0.
  • The (2 + k)-th line (1 \leq k \leq M) contains U_k and V_k, separated by a space, indicating that employee U_k must present before employee V_k.

Output

Output in a single line the maximum total score among all presentation orders that satisfy all constraints.

Sample Input 1

3 1
1 2 3
1 2

Sample Output 1

14

Sample Input 2

3 1
3 1 2
1 3

Sample Output 2

13

Sample Input 3

5 3
5 3 8 1 6
4 1
4 2
3 5

Sample Output 3

84

Sample Input 4

8 4
10 20 30 40 50 60 70 80
1 2
3 4
5 6
7 8

Sample Output 4

2040

Sample Input 5

1 0
42

Sample Output 5

42