시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 111 52 40 43.011%

문제

홍준이는 물리를 좋아하고 밀도 계산이 취미에요.

학교에서 그래프 이론을 배운 홍준이는 그래프 상에서 밀도를 정의해보기로 했어요. 정점과 간선에 가중치가 있는 무방향 그래프에서 밀도는 정점들의 가중치 합을 SumV라 하고, 간선들의 가중치 합을 SumE라 하면, (SumV / SumE)로 정의됩니다.

홍준이는 명우에게 생일 선물로 정점과 간선에 가중치가 있는 무방향 그래프를 하나 선물 받았습니다. 심심한 홍준이는 원래 그래프의 부분 그래프인 ‘유도 부분그래프’(induced subgraph)에서 밀도를 최대가 되는 유도 부분그래프를 찾고 싶습니다.

그래프 G(V, E)의 유도 부분그래프 G’(V’, E’)는 다음과 같은 조건들을 만족합니다.

  1. V' ⊆ V
  2. (정점 u와 v를 잇는 간선) ∈ E'  if and only if u ∈ V', v ∈ V', (정점 u와 v를 잇는 간선) ∈ E
  3. G’에서의 정점과 간선의 가중치는 G에서와 동일합니다.
  4. G’은 연결 그래프입니다.

홍준이를 도와 밀도가 최대가 되는 유도 부분그래프를 구해주세요.

입력

첫째 줄에 정점의 개수를 나타내는 n과 간선의 개수를 나타내는 m이 주어집니다.

둘째 줄에 i번째 정점의 가중치를 나타내는 n개의 정수가 공백을 사이에 두고 주어집니다.

셋째 줄부터 간선의 정보를 나타내는 3개의 정수가 m개의 줄에 걸쳐서 주어집니다.

정점의 개수는 1개 이상 500개 이하이며, 간선의 개수는 0개 이상 n(n-1)/2개 이하입니다. 중복되는 간선은 주어지지 않습니다. 정점의 가중치는 1보다 크거나 같고 1,000,000보다 작거나 같으며, 간선의 가중치는 1보다 크거나 같고 1,000보다 작거나 같습니다. 그래프에서 정점의 번호는 1번부터 n번까지 순서대로 매겨져 있습니다.

출력

밀도가 최대가 되는 유도 부분그래프의 밀도를 소수 6번째 자리까지 출력한다.

예제 입력 1

2 1
1 2
1 2 1

예제 출력 1

3.000000