주방 케이블 대혼란

새 프로젝트를 시작했다. 바로 홈 오토메이션 시스템 설치다. 필요한 부품은 모두 샀고, 동네 전자 상점에서 서로 길이가 다른 케이블 여러 개가 들어 있는 행사 세트도 구했다. 이제 컨트롤러와 몇 미터 떨어진 스마트 샌드위치 메이커를 연결하려는데, 충분히 긴 케이블이 하나도 없다.

이 문제를 해결하려면 케이블 몇 개를 이어서 긴 케이블 하나를 만들어야 한다. 가지고 있는 모든 케이블의 길이를 측정했다. 케이블마다 양 끝에서 정확히 5센티미터씩 피복이 벗겨져 있다. 두 케이블을 연결하려면 벗겨진 끝을 겹쳐서 꼬아야 한다. 겹치는 길이가 0이어도 두 케이블이 서로 닿기만 하면 연결된 것으로 본다. 겹치는 길이는 5센티미터를 넘을 수 없지만, 많이 겹칠수록 연결 품질이 좋아진다. 컨트롤러 쪽과 샌드위치 메이커 쪽에도 각각 5센티미터의 벗겨진 끝이 있고, 여기에 새로 만든 케이블을 같은 방식으로 연결해야 한다. 링크의 연결 품질은 사용한 겹침 중 가장 작은 값으로 정해지며, 이 값을 최대화하는 것이 목표다.

문제는 여기서 아주 쉬워지겠지만, 완벽주의자인 룸메이트가 케이블을 불필요하게 쓰는 것을 싫어한다. 따라서 케이블은 고리나 우회 없이 곧은 선을 이루어야 한다. 케이블을 자르는 것도 당연히 안 된다.

그림 K.1: 길이가 다른 케이블 네 개가 컨트롤러와 샌드위치 메이커를 연결하며, 겹침의 길이는 각각 다르다. 연결 1은 겹침이 가장 크고, 연결 2는 겹침이 가장 작으며, 나머지 연결은 그 사이에 있다. 이 배치의 품질은 0이다.

케이블을 배치하는 모든 방법 중에서 품질이 가장 좋은 것을 찾아라.

입력은 다음과 같다.

• 두 정수 n, g (1 ≤ n ≤ 60, 11 ≤ g ≤ 1 000)가 있는 한 줄. n은 케이블의 수이고, g는 컨트롤러와 샌드위치 메이커의 케이스 사이 거리를 센티미터로 나타낸 값이다.
• n개의 줄. 각 줄에는 정수 d (11 ≤ d ≤ 1 000)가 있으며, 케이블의 길이(벗겨진 끝 포함)를 나타낸다.

n개의 케이블은 각각 최대 한 번만 사용할 수 있다.

얻을 수 있는 최고 품질을 하나의 수로 출력한다. 품질은 상대 오차 또는 절대 오차 중 더 작은 값이 10−7 이하가 되도록 정확해야 한다. 조건을 만족하는 배치가 없으면 impossible을 출력한다.