Rikka와 책

Rikka의 책상 위에 책이 $n$권 있다. $i$번째 책의 길이, 너비, 높이, 무게는 각각 $l\_i$, $1$, $1$, $w\_i$이다. 길이가 $l\_i$인 두 면을 긴 변이라 하고, 길이가 $1$인 두 면을 짧은 변이라 한다. 각 책의 질량은 부피 전체에 고르게 분포한다.

Rikka는 오늘 이 책들을 책상 위에 쌓으려 한다. 총 $n$번의 차례로 쌓으며, 각 차례마다 아직 남은 책 중 하나를 골라 직전에 쌓은 책의 바로 위에 올린다. 첫 번째 책은 책상 위에 바로 놓는다.

가지런하게 쌓기 위해 Rikka는 다음 네 가지 조건을 정했다.

• 모든 책의 왼쪽 긴 변은 같은 평면 위에 있다. 오른쪽 긴 변도 마찬가지다.
• 왼쪽 긴 변들이 이루는 평면은 지면에 수직이다. 오른쪽 긴 변도 마찬가지다.
• 모든 책의 짧은 변은 책상의 가장자리와 평행하다.
• 최종적으로 쌓인 책 더미는 안정해야 한다. 두꺼운 책이 쓰러지면 위험하다.

대략적인 모습은 다음 그림과 같다.

재미를 위해 Rikka는 책 더미가 최대한 기이해 보이도록 쌓으려 한다. 각 책의 기이함은 책의 앞쪽 짧은 변이 책상 밖으로 나간 수평 거리로 정의한다. 책 더미의 기이함은 모든 책의 기이함 중 최댓값이다. 예를 들어 위 그림에서 책 더미의 기이함은 선분 TU의 길이와 같다.

Rikka는 책 더미의 기이함이 최대가 되도록 쌓는 계획을 찾아라.

추가 가정은 다음과 같다.

• 중력 계수는 일정하며, 높이가 바뀌어도 변하지 않는다고 본다.
• 책상과 책의 모양은 바뀌지 않는다고 본다.

첫째 줄에 책의 수 $n\ (1 \leq n \leq 20)$이 주어진다.

둘째 줄에 각 책의 길이 $l\_i\ (1 \leq l\_i \leq 10^3)$가 $n$개의 정수로 주어진다.

셋째 줄에 각 책의 무게 $w\_i\ (1 \leq w\_i \leq 10^3)$가 $n$개의 정수로 주어진다.

책 더미 기이함의 최댓값을 나타내는 실수 하나를 한 줄에 출력한다.

답의 절대 오차 또는 상대 오차는 $10^{-9}$보다 작아야 한다.

첫 번째 예제에서 최적 계획은 다음 그림과 같다.

1, 2, 3, 4번 책의 기이함은 각각 $\frac{1}{4}, \frac{25}{12}, \frac{7}{12}, \frac{13}{12}$이다. 따라서 책 더미의 기이함은 $\frac{25}{12}$이다.