정점이 \(N\)개인 무방향 그래프가 있다. 이 그래프에는 \(M\)개의 간선이 있으며, 각 간선에는 \(1\)부터 \(K\) 사이의 색깔 하나가 칠해져 있다.

당신은 간선들의 부분집합 \(T\)를 고르려 한다. 단, \(T\)는 다음 두 조건을 모두 만족해야 한다.

• \(T\)에 포함된 간선들은 사이클을 이루지 않는다 (즉, \(T\)는 숲을 이룬다).

• 각 색 \(i\)에 대해, \(T\)에 포함된 색 \(i\) 간선의 개수가 \(c_i\)를 넘지 않는다.

이 두 조건을 동시에 만족하면서 고를 수 있는 간선의 최대 개수를 구하라.

\(1 \le N \le 400\)

\(0 \le M \le 400\)

\(1 \le K \le M\) (단 \(M = 0\)이면 \(K = 1\))

\(0 \le c_i \le M\)

첫 줄에 정점 수 \(N\), 간선 수 \(M\), 색의 수 \(K\)가 주어진다.

둘째 줄에 \(K\)개의 정수 \(c_1, c_2, \dots, c_K\)가 주어진다 (색 \(i\)의 사용 한도).

이어서 \(M\)개의 줄에 각각 세 정수 \(u\), \(v\), \(w\)가 주어지며, 정점 \(u\)와 \(v\)를 잇는 색 \(w\)의 간선을 뜻한다 (\(1 \le u, v \le N\), \(u \neq v\), \(1 \le w \le K\)). 같은 정점 쌍 사이에 색이 다른 여러 간선이 있을 수 있다.

조건을 만족하며 고를 수 있는 간선의 최대 개수를 한 줄에 출력한다.

riseoj 작성

출처 Original