게임 레벨 나누기

아름이는 레벨 $n$개로 이루어진 컴퓨터 게임을 한다. 레벨에는 $1$번부터 $n$번까지 번호가 붙어 있다.

$n$개의 레벨은 그룹 $k$개로 나뉜다. 각 그룹은 연속한 레벨로 이루어지고, 모든 레벨은 정확히 한 그룹에 속하며, 빈 그룹은 없다.

게임은 다음 과정을 반복한다.

1. 모든 레벨을 깼으면 게임이 끝난다. 그렇지 않으면 시스템은 아직 깨지 못한 레벨이 하나 이상 남아 있는 첫 번째 그룹을 찾는다. 이 그룹을 $X$라고 한다.
2. 시스템은 코인을 담을 빈 가방을 하나 만든다. 코인 하나는 레벨 하나를 나타내고, 같은 레벨을 나타내는 코인이 여러 개 들어갈 수 있다.
   • 그룹 $X$에서 이미 깬 레벨 $i$마다, 레벨 $i$를 나타내는 코인 $t_i$개를 가방에 넣는다.
   • 그룹 $X$에서 아직 깨지 못한 첫 번째 레벨을 $j$라고 하면, 레벨 $j$를 나타내는 코인 $t_j$개를 가방에 넣는다.
3. 시스템은 가방에 든 코인 중 하나를 같은 확률로 무작위로 고르고, 그 코인이 나타내는 레벨을 아름이에게 알려 준다. 아름이는 그 레벨을 한 시간 동안 플레이해 반드시 깬다. 이미 깬 레벨이 나와도 한 시간을 그대로 쓰며, 깬 레벨의 상태는 바뀌지 않는다.

게임이 끝날 때까지 걸리는 시간의 기댓값은 레벨을 어떻게 나누는지에 따라 달라진다. $n$, $k$, $t_1, t_2, \dots, t_n$이 주어졌을 때, 기댓값이 가장 작아지도록 나눴을 때의 기댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 $n$과 $k$가 주어진다. ($1 \le n \le 200\,000$, $1 \le k \le \min(50, n)$)

둘째 줄에 $t_1, t_2, \dots, t_n$이 주어진다. ($1 \le t_i \le 100\,000$)

기댓값의 최솟값을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 자리가 모자라면 $0$으로 채워 항상 여섯 자리를 쓴다.

첫 번째 예제에서는 레벨 $1$을 한 그룹으로 두고 나머지 레벨을 다른 한 그룹으로 두는 것이 최적이다.

두 번째 예제에서는 레벨 세 개씩 두 그룹으로 나누는 것이 최적이다.