AT_jsc2024_final_f Max of Sum of Reachable Min

$ 1 $ から $ N $ までの番号がついた $ N $ 頂点からなる DAG が与えられます． 辺は $ M $ 本あり， $ i $ 番目の辺は頂点 $ U_i $ から頂点 $ V_i $ に向かう辺です． ここで， $ U_i

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $

各 $ K=1,2,\cdots,N $ に対する答えをこの順に出力せよ．

### Sample Explanation 1 各 $ 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\} $ ### Constraints - $ 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 $ ) - 入力される値はすべて整数