반짝반짝

겨울 기분이 조금밖에 남지 않은 지금, 수현이는 크리스마스 트리를 장식하려고 한다.

크리스마스 트리는 전구 스트립으로 두른다. 전구 스트립에는 전구 $N$개가 일(一)자로 설치되어 있고, 왼쪽에 전원을 넣는다. 이 전구 스트립은 전구 하나가 고장 나면 고장 난 전구를 시작으로 오른쪽에 설치된 모든 전구에 불이 들어오지 않는다.

수현이는 반짝반짝한 것을 좋아한다. 그래서 전구 스트립을 최대 $K$개의 토막으로 자르고, 왼쪽에 전원을 각각 다시 넣어 트리를 장식하려고 한다. 이렇게 해서 불이 들어온 전구 개수의 기댓값이 최대가 되게 하고 싶다. 각 전구가 고장 날 확률이 주어질 때, 불이 들어온 전구 개수의 기댓값의 최댓값을 계산하라.

다음과 같이 입력이 주어진다.

$N\ K$

$p_1\ p_2\ \dots\ p_N$

불이 들어온 전구 개수의 기댓값의 최댓값을 출력한다.

출력한 값과 정답의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하여야 한다.

• $N$은 전구 스트립의 길이이다. ($1 \leq N \leq 2\,500$)
• $1 \leq K \leq \min \left\{ N, 10 \right\}$
• $p_i$는 전구가 고장 날 확률이며, 소수점 아래 두 자리까지 주어진다. 왼쪽 전구에서 오른쪽 전구 순서로 주어진다. ($0 \leq p_i \leq 1$)
• $N$과 $K$는 정수다.