某個計劃有 \(n\) 項工作，以 \(1 \sim n\) 編號，工作之間有前置關係。我們用一個點代表一項工作，以邊 \( (a, b) \) 表示 \(a\) 是 \(b\) 的前置工作，也就是說 \(a\) 完成之後，工作 \(b\) 才能開始。

每一項工作 \(v\) 有一個需求的工作時間 \(w[v]\)，代表該工作至少需要耗時 \(w[v]\) 才能完成。

本題要計算此計畫的最早完工時間，也就是計畫開始後，最早可以完成所有工作的時間。此外，對於某個工作，如果該工作的任何延誤都會讓整個計畫的最早完工時間延後，這個工作就稱為關鍵工作，否則稱為非關鍵工作。

例子

假設 \(n = 3\)，前置關係有 \((1, 3)\) 與 \((2, 3)\)，代表：

• 工作 \(1\) 完成後才可以開始工作 \(3\)。
• 同樣地，工作 \(2\) 完成後才可以開始工作 \(3\)。

需求工時為：

\begin{aligned} w[1] &= 1 \ w[2] &= 3 \ w[3] &= 4 \end{aligned}

我們可以看得出：

• 工作 \(1\) 與 \(2\) 可以平行作業。
• 時間 \(1\) 時，工作 \(1\) 可以完成。
• 時間 \(3\) 時，工作 \(2\) 可以完成。

因此，工作 \(3\) 最早可以在時間 \(3\) 開始，而最早的完工時間為：

\( 3 + 4 = 7\)

在這三項工作中：

• 工作 \(2\) 與 \(3\) 是關鍵工作。
• 工作 \(1\) 不是關鍵工作，因為工作 \(1\) 只要不花超過 \(3\) 的工時（即延誤不超過 \(2\)），就不會影響整個計劃的最早完工時間。

輸入格式

第一行是兩個正整數 \( n \) 與 \( m \) ，代表工作數與前置關係數，點以 \( 1 \)  ～ \(n\)編號， 第二行是 \( n \) 個正整數，依序代表每一個工作的需求工時 \( w[v]\) ，接下來有 \( m \) 行，每行 兩個整數 \( u \) 與 \( v\) ，代表 \( u \) 是 \( v \) 的前置工作。 \(n\) 不超過 \(1e4，m\) 不超過 \(1e5，w\) 不超過 \(1e3\) 。輸入保證有解。

輸出格式

第一行輸出最早完工時間， 第二行輸出那些工作是關鍵工作，輸出時依照工作的編號由小到大，相鄰兩數字之間以一個空白分格。

範例輸入 1

3 2
1 3 4
1 3
2 3

範例輸出 1

7
2 3

範例輸入 2

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

範例輸出 2

8
1 3 4