네트워크 플래닝

정유 회사의 이익은 주유소를 어디에 세우느냐에 따라 크게 달라진다. 이 회사는 이익을 최대로 만들려고 네트워크 플래닝이라고 부르는 방법으로 새 주유소를 세울 도시를 고른다.

당신은 이 회사의 컨설턴트다. 회사는 도시의 수와 도시를 잇는 도로, 도시마다의 연료 수요량, 이미 주유소가 있는 도시 목록, 올해 새로 지어야 하는 주유소의 개수를 넘겨준다. 회사가 원하는 답은 어느 도시에 새 주유소를 지어야 공급량이 가장 커지는지다.

규칙은 다음과 같다.

• 도시는 $N$개이고, 한 도시에는 주유소를 하나만 둘 수 있다.
• 주유소 한 곳이 공급하는 연료의 양에는 상한이 없다.
• 주유소는 자기 도시 수요의 70%를 공급하고, 이웃한 도시마다 그 도시 수요의 10%를 더 공급한다. 이웃 도시에 주유소가 있든 없든 이 값은 달라지지 않는다.
• 예를 들어 도시 A, B, C가 서로 이웃이고 A와 B에 주유소가 있다면, A의 주유소는 A 수요의 70%와 B 수요의 10%, C 수요의 10%를 공급한다. B의 주유소도 같은 방식으로 공급한다.
• 지형 때문에 한 도시의 이웃은 최대 세 곳이다.
• 회사의 총수익은 공급한 연료의 총량에 정비례한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. ($T \le 10$)

각 테스트 케이스의 첫 줄에는 도시의 수 $N$이 주어진다. ($1 \le N \le 100000$)

이어지는 $N$개의 줄에는 도시 $i$의 연료 수요량 $D_i$가 리터 단위로 한 줄에 하나씩 주어진다. ($0 \le D_i \le 1000$)

다음 줄에는 도로의 수 $E$가 주어진다.

이어지는 $E$개의 줄에는 서로 이웃한 두 도시의 번호 $C_1$과 $C_2$가 주어진다. 도로는 양방향이고 같은 도로가 두 번 주어지지 않는다. 즉 $(C_1, C_2)$가 주어졌다면 같은 테스트 케이스에 $(C_2, C_1)$은 없다. 도시 번호는 1번부터 $N$번까지다. 한 도시의 이웃이 최대 세 곳이므로 $E \le \lfloor 3N/2 \rfloor$이다.

다음 줄에는 주유소가 이미 있는 도시의 수 $S$가 주어진다. ($0 \le S < N$)

이어지는 $S$개의 줄에는 주유소가 이미 있는 도시의 번호가 한 줄에 하나씩 주어진다.

마지막 줄에는 올해 새로 지어야 하는 주유소의 개수 $M$이 주어진다. ($1 \le M \le N - S$) 정확히 $M$개를 지어야 한다.

테스트 케이스마다 두 줄을 출력한다.

첫 줄에는 기존 주유소와 새로 지은 주유소가 함께 공급하는 연료의 최대 총량을 정수로 출력한다. 이 총량은 항상 0.1리터의 배수이므로 소수 첫째 자리에서 반올림하고, 소수 부분이 정확히 0.5이면 올린다.

둘째 줄에는 새로 주유소를 지어야 하는 도시의 번호를 증가하는 순서로 공백 하나씩 두고 출력한다. 이미 주유소가 있는 도시는 이 목록에 넣지 않는다. 최대 총량을 만드는 방법이 여러 가지라면, 번호를 증가하는 순서로 나열했을 때 사전순으로 가장 앞서는 것을 출력한다.

첫 번째 예제에는 테스트 케이스가 두 개 들어 있다. 앞의 테스트 케이스에서는 도시 3에만 새 주유소를 지어야 총 공급량이 360리터로 가장 커진다.

뒤의 테스트 케이스에는 최적해가 두 개 있다. 도시 1, 2, 5에 짓는 것과 도시 1, 3, 5에 짓는 것의 공급량이 같으므로, 사전순으로 앞서는 1 2 5를 출력해야 한다. 이때 도시 1은 268.2리터, 도시 2는 182.6리터, 도시 5는 290리터를 공급하고, 이미 주유소가 있는 도시 4는 150리터를 공급한다. 합이 268.2 + 182.6 + 290 + 150 = 890.8이므로 반올림한 891을 출력한다.