잠수부

잠수부 여러 명이 동굴을 빠져나가려고 한다. 밖으로 나가려면 모든 잠수부가 커다란 바위 아래를 헤엄쳐 지나가야 하는데, 바위 아래를 지나가려면 이들이 함께 쓰는 단 하나뿐인 전등이 필요하다. 바위 아래 통로는 좁아서 한 번에 최대 두 명까지만 함께 지나갈 수 있다.

잠수부들은 모두 밖으로 나갈 때까지 다음 과정을 반복한다.

• 두 잠수부가 전등을 들고 함께 바위 아래를 지나간다.
• 그런 다음 방금 건넌 그 두 사람 중 한 명이 전등을 들고 다시 바위 아래로 되돌아와, 다음 잠수부들이 전등을 쓸 수 있게 한다. (맨 마지막으로 건널 때는 되돌아올 필요가 없다.)

각 잠수부의 헤엄 속도는 일정하다. 두 사람이 함께 지나가면 둘 중 더 느린 사람의 속도에 맞추므로, 두 사람이 함께 건너는 데 걸리는 시간은 두 사람의 시간 중 더 큰 값이다. 한 사람이 혼자 되돌아오는 데 걸리는 시간은 그 사람 자신의 시간이다.

일부 잠수부 쌍은 서로 사이가 좋지 않아 함께 바위 아래를 지나가려 하지 않는다. 그런 쌍은 절대 둘이 함께 건널 수 없다.

모든 잠수부가 동굴을 빠져나가는 데 필요한 가장 짧은 전체 시간을 구하라. 불가능하다면 불가능하다고 답하라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 100000$, $0 \le m \le \min(100000,\ n(n-1)/2)$). 각각 잠수부의 수와 서로 싫어하는 쌍의 수이다.

둘째 줄에 $n$개의 정수 $t_1, t_2, \ldots, t_n$이 공백으로 구분되어 주어진다 ($1 \le t_i \le 500000000$). $t_i$는 $i$번 잠수부가 바위 아래를 지나가는 데 걸리는 시간이다.

다음 $m$개의 줄에는 각각 두 정수 $a$와 $b$가 주어진다 ($1 \le a, b \le n$, $a \ne b$). 서로 싫어하여 함께 바위 아래를 지나가지 않으려는 잠수부 쌍을 나타낸다. 순서를 구분하지 않는 각 쌍 $\{a, b\}$는 입력에 최대 한 번만 나타난다.

한 줄에 정수 하나를 출력한다. 모든 잠수부가 동굴을 빠져나가는 데 걸리는 가장 짧은 전체 시간이다. 규칙에 따라 모두가 빠져나가는 것이 불가능하면 대신 IMPOSSIBLE을 출력한다.