Màn chơi và các vùng

Một trò chơi điện tử có $n$ màn chơi, đánh số từ $1$ đến $n$. Các màn được chia thành $k$ vùng. Mỗi vùng là một nhóm gồm một số màn liên tiếp (khác rỗng), và mỗi màn thuộc đúng một vùng.

Trò chơi lặp lại quá trình sau:

1. Nếu tất cả các vùng đã hoàn thành thì trò chơi kết thúc. Ngược lại, hệ thống tìm vùng đầu tiên còn ít nhất một màn chưa hoàn thành. Gọi vùng đó là $X$.
2. Hệ thống tạo một túi thẻ (ban đầu rỗng). Mỗi thẻ đại diện cho một màn (có thể có nhiều thẻ cùng đại diện một màn):
   • Với mỗi màn $i$ đã hoàn thành trong vùng $X$, hệ thống bỏ vào túi $t_i$ thẻ đại diện cho màn $i$.
   • Gọi $j$ là màn chưa hoàn thành đầu tiên trong vùng $X$. Hệ thống bỏ vào túi $t_j$ thẻ đại diện cho màn $j$.
3. Hệ thống rút ngẫu nhiên đều một thẻ trong túi, người chơi bắt đầu màn ứng với thẻ đó. Người chơi tốn đúng một giờ và hoàn thành màn đó (kể cả khi màn này đã từng được hoàn thành trước đây).

Cho $n$, $k$ và các giá trị $t_1,t_2,\dots ,t_n$, hãy chia các màn thành các vùng sao cho kỳ vọng số giờ cần để kết thúc trò chơi là nhỏ nhất. In ra giá trị kỳ vọng nhỏ nhất đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$: số màn chơi và số vùng.
• Dòng thứ hai chứa $n$ số nguyên $t_1,t_2,\dots ,t_n$.

Dữ liệu ra

• In ra một số thực: kỳ vọng số giờ nhỏ nhất khi các màn được chia vùng tối ưu.

Đáp án được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án chuẩn không vượt quá ${10}^{-4}$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le k\le min(50,n)$
• $1\le t_i\le {10}^5$

Ví dụ