問題文

1 から N までの番号がついた N 頂点からなる DAG が与えられます． 辺は M 本あり，i 番目の辺は頂点 U_i から頂点 V_i に向かう辺です． ここで，U_i<V_i が保証されます． 各頂点には整数が書かれており，頂点 i には整数 A_i が書かれています．

頂点の部分集合 s に対し，f(s) を以下のように定めます．

• f(s)=\sum_{v \in s} \min\{A_u\ |\ u \in s かつ DAG において頂点 u から頂点 v へ移動できる \}

各整数 K=1,2,\cdots,N について，以下の問題に答えてください．

頂点集合 \{1,2,\cdots,N\} を K 個の (空でもよい) 部分集合に分解し，それらを X_1,X_2,\cdots,X_K とおきます． 分解の際，各頂点がちょうど 1 つの部分集合に含まれるようにします． \sum_{1 \leq i \leq K}f(X_i) としてありうる最大値を求めてください．

制約

• 1 \leq N \leq 80
• 0 \leq M \leq 160
• 1 \leq A_i \leq 80
• 1 \leq U_i < V_i \leq N
• (U_i,V_i) \neq (U_j,V_j) (i \neq j)
• 入力される値はすべて整数

入力例 1

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

出力例 1

4 8 10 10

各 K に対する最適解（の一例）は以下のとおりです．

• K=1 : X_1=\{1,2,3,4\}
• K=2 : X_1=\{1\},X_2=\{2,3,4\}
• K=3 : X_1=\{1\},X_2=\{2,3\},X_3=\{4\}
• K=4 : X_1=\{1\},X_2=\{2\},X_3=\{3\},X_4=\{4\}

入力例 2

10 9
22 7 20 26 1 11 7 1 15 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

出力例 2

49 104 120 120 120 120 120 120 120 120

入力例 3

15 13
20 12 14 20 22 20 26 34 40 42 44 60 45 69 73
1 14
2 5
2 8
2 9
2 12
2 15
4 7
6 12
7 9
8 15
10 15
11 12
13 14

出力例 3

317 513 541 541 541 541 541 541 541 541 541 541 541 541 541

入力例 4

20 31
54 12 12 26 7 6 38 51 29 52 70 49 67 65 80 67 54 77 74 73
1 2
2 3
3 4
1 5
2 6
5 6
3 7
6 7
4 8
7 8
5 9
6 10
9 10
7 11
10 11
8 12
11 12
9 13
10 14
13 14
11 15
14 15
12 16
15 16
13 17
14 18
17 18
15 19
18 19
16 20
19 20

出力例 4

190 749 872 935 961 963 963 963 963 963 963 963 963 963 963 963 963 963 963 963