은 쟁탈전

Piet Hein은 네덜란드 연합주와 스페인이 맞붙은 80년 전쟁 시기의 네덜란드 해군 장교다. 가장 유명한 전과는 1628년 쿠바 근해에서 은 함대(Zilvervloot)를 나포한 일이다. 이 함대는 아메리카 대륙의 스페인 식민지에서 본국으로 은을 실어 가던 배로 이루어져 있었다. 전투 기록이 자세히 남아 있지 않아 아래 설명에는 역사적 사실과 다른 부분이 있을 수 있다.

은 함대의 배에는 은화가 실려 있다. Piet Hein의 작전은 단순하다. 함대에서 배 몇 척을 끌고 나와 그 안의 은화를 차지한다.

네덜란드군을 막으려고 스페인은 함대의 모든 배를 굵은 쇠사슬로 서로 묶었다. 배는 저마다 다른 배 한 척 이상과 사슬로 이어지고, 두 배 사이에는 사슬이 많아도 한 개만 놓이며, 사슬이 엉켜 매듭이 되지 않도록 서로 교차하지 않게 배치했다. 그래서 배와 사슬은 연결된 평면 그래프를 이룬다.

이 조치는 오히려 스페인에게 불리하게 작용했다. 노련한 장교인 Piet Hein은 끌고 나갈 배 무리 안의 어느 두 배든 사슬로 직접 이어져 있으면 예인이 가장 쉽다는 사실을 알고 있었다. 그는 이런 무리를 사슬군이라고 불렀다.

Piet Hein은 은화가 가장 많은 사슬군을 고른 다음, 정확한 포격으로 나머지 배와 이어진 사슬을 끊고 그 사슬군의 배를 모두 끌고 가라고 명령했다. 사슬군의 전리품은 그 사슬군을 이루는 배에 실린 은화의 총합이다.

함대를 그래프로 그리면 점 하나는 배 한 척이고, 선 하나는 두 배를 잇는 사슬 하나다. 은 함대의 정보가 주어질 때, 전리품이 가장 많은 사슬군의 은화 총합을 구하라.

입력은 여러 테스트 케이스로 이루어지고 파일이 끝날 때까지 이어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 함대의 배 수 $v$ ($2 \le v \le 450$)와 사슬 수 $e$ ($1 \le e \le 900$)가 주어진다.
• 다음 $v$개 줄에 $S_1, S_2, \dots, S_v$가 한 줄에 하나씩 주어진다. $S_i$는 $i$번 배에 실린 은화의 수이고, $100 \le S_i \le 6000$인 양의 정수다.
• 다음 $e$개 줄에 사슬 하나가 잇는 두 배의 번호 $c_{start}$와 $c_{end}$가 주어진다 ($1 \le c_{start} < c_{end} \le v$).

모든 함대는 연결된 평면 그래프를 이룬다.

각 테스트 케이스마다 Piet Hein이 빼앗는 은화의 수를 한 줄에 하나씩 출력한다.