파티 기획자 유나는 손님 \(N\) 명 중 일부를 초대하려 한다. \(i\) 번째 손님을 초대하면 분위기 점수 \(w_i\) 를 얻는다. 그런데 어떤 두 손님은 사이가 나빠 둘을 동시에 초대할 수 없다.

사이가 나쁜 쌍이 \(E\) 개 주어진다. 같이 초대하면 안 되는 쌍이 한 쌍도 포함되지 않도록 손님들을 골랐을 때, 얻을 수 있는 분위기 점수 합의 최댓값을 구하여라. 아무도 초대하지 않으면 점수는 \(0\) 이다.

• \(1 \le N \le 20\)
• \(0 \le E \le \frac{N(N-1)}{2}\)
• \(1 \le w_i \le 100{,}000\)
• 같은 쌍은 두 번 주어지지 않는다.

첫째 줄에 손님 수 \(N\) 과 사이가 나쁜 쌍의 수 \(E\) 가 주어진다.

둘째 줄에 \(N\) 개의 분위기 점수 \(w_1, \dots, w_N\) 이 주어진다.

이어지는 \(E\) 개의 줄에 각각 사이가 나쁜 두 손님의 번호 \(a\), \(b\) (\(1 \le a < b \le N\)) 가 주어진다.

초대할 손님들의 분위기 점수 합의 최댓값을 한 줄에 출력한다.

riseoj 작성

출처 Original