그 러시아 해커들

선거는 $k \cdot n$초 동안 진행됩니다. 시간은 이산적으로 생각하며, 0부터 $k \cdot n - 1$까지 번호가 붙은 $k \cdot n$개의 시간 단위가 있습니다. 모든 사건은 정수 개의 시간 단위를 차지합니다.

선거 시간은 길이가 같은 $k$개의 시간 구간으로 나뉩니다. 0초부터 $n - 1$초까지, $n$초부터 $2n - 1$초까지 이런 식으로 이어집니다. 보안 프로그램은 선거가 시작하는 순간부터 동작하며, 각 구간마다 보안 검사를 한 번씩 수행합니다. 각 검사는 정확히 1초가 걸립니다. 검사가 일어나는 초는 무작위로 정해지며, $i \cdot n + j$초에 검사가 일어날 확률은 $p_j$입니다. 서로 다른 구간의 검사 시각은 서로 독립입니다.

아무 초에나 로그인할 수 있고, 그 뒤에는 무작위 시간의 해킹 작업이 필요합니다. 작업이 $j$초 걸릴 확률은 $q_j$이며, 이 값은 보안 검사와 독립입니다. 로그인은 한 번만 할 수 있으므로, 일단 로그인하면 작업을 끝내야 합니다.

보안 프로그램은 검사가 끝날 때마다 메시지를 보냅니다. 메시지를 받은 직후 다음 초에 로그인할 수 있습니다. 로그인한 상태에서 보안 검사가 일어나는 초가 하나라도 있으면 선거가 중단되어 실패합니다. 선거 시간 안에 작업을 끝내지 못해도 실패합니다.

최선의 전략을 택했을 때 성공할 확률을 구하세요.

첫 줄에는 각 구간의 길이 $n$과 보안 검사의 횟수 $k$가 주어집니다 ($2 \leq n \leq 300\,000$, $1 \leq k \leq 300\,000$).

둘째 줄에는 구간 안에서 검사가 일어나는 정확한 초의 분포 $p_0, p_1, \ldots, p_{n-1}$ ($0 \leq p_i \leq 1$, $\sum_{i=0}^{n-1} p_i = 1$)이 실수 $n$개로 주어집니다.

셋째 줄에는 해킹 시간의 분포 $q_1, q_2, \ldots, q_{2n-2}$ ($0 \leq q_i \leq 1$, $\sum_{i=1}^{2n-2} q_i = 1$)이 실수 $2n-2$개로 주어집니다.

모든 확률은 소수점 아래 여섯 자리 이하로 주어집니다.

성공 확률의 최댓값을 출력하세요. 절대 오차가 $10^{-6}$ 이하이면 정답으로 인정합니다.

첫 번째 예제에서는 보안 검사가 한 번뿐입니다. 최선의 전략은 검사가 끝나기를 기다렸다가 로그인하고, 시간이 다 되기 전에 해킹을 시도하는 것입니다. 성공 확률은 $0.5 \cdot (0.75 + 0.25) + 0.25 \cdot 0.75 + 0.25 \cdot 0 = 0.6875$입니다.

두 번째 예제에서는 해킹에 항상 정확히 4초가 걸립니다. 검사 결과와 관계없이 2초에 로그인해서 4초까지 끝내야 합니다. 첫 검사가 0초, 두 번째 검사가 5초에 일어날 때만 성공하므로 확률은 $0.3 \cdot 0.3 = 0.09$입니다.

세 번째 예제에서는 항상 1초에 해킹을 시작하는 것이 최선이며, 이때 성공 확률은 0.8입니다.