오케스트라 최적화

문제 해결사 오케스트라는 프로그래머이자 음악가인 사람들의 모임으로, 다가오는 순회공연을 한창 계획하고 있다. 가장 중요한 과제는 최적의 관객 호응을 얻기 위해 각 곡에서 낼 수 있는 소음을 최대화하는 것이다.

오케스트라는 $N$명의 음악가로 구성되어 있으며, $M$개의 박자로 이루어진 곡을 최적화해 달라고 요청했다. 각 음악가는 자신이 흥미롭다고 생각한 박자만 연습했으며, 나머지 박자는 연주할 수 없다. 음악가가 박자 하나를 연주할 때마다 $V=1/(X+1)$ 소음 단위의 소음을 내는데, 여기서 $X$은 그 음악가가 곡에서 이전에 연주한 박자의 수이다. 따라서 음악가는 더 많은 박자를 연주할수록 점점 약하게 연주하며, 이는 당연히 악기를 들어 올리는 데 드는 수고 때문이다.

한 박자의 소음은 그때 연주하는 음악가들의 $V$ 중 최댓값으로 계산하거나(가장 크게 연주하는 사람의 소리만 들린다), 그 박자에 아무도 연주하지 않으면 $0$로 계산한다. 곡의 전체 소음을 계산하려면 모든 박자의 소음을 단순히 합한다. 오케스트라가 최적으로 연주할 때 곡에서 낼 수 있는 소음의 양을 계산하는 것이 과제이다.

모든 음악가는 똑같이 잘 연주하며, 음악가가 낼 수 있는 소음의 양에 영향을 미치는 유일한 요소는 그 음악가가 이전에 연주한 박자의 수임에 유의한다.

점수

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ |$20$| $N, M \leq 20$

$2$ |$80$| 추가 제한 없음.

첫째 줄에는 두 정수 $N$과 $M$가 주어진다. ($1 \leq N \leq 1000$, $20 < M \leq 1000$).

이후 음악가 한 명을 설명하는 줄이 $N$개 주어진다. 각 줄은 해당 음악가가 연습한 박자의 수를 나타내는 정수 $T_i$으로 시작하며, 이어서 음악가가 연습한 박자를 나타내는 정수 $T_i$개가 주어진다. 각 박자는 $1$에서 $M$ 사이의 수로 표현된다. 또한 모든 $T_i$의 합이 $20000$보다 작음이 보장된다.

곡에서 낼 수 있는 최대 소음을 부동소수점 수로 출력한다. 절대 오차가 $10^{-5}$보다 작으면 정답으로 간주한다.

두 사람과 다섯 개의 박자가 있다고 하자. 사람 1은 모든 박자를 연주할 수 있고, 사람 2는 처음 두 박자만 연주할 수 있다(예제 입력 1 참조). 그러면 두 번째 사람이 자신이 연주할 수 있는 두 박자를 연주하게 하고, 첫 번째 사람이 나머지를 연주하게 한다. 이때 모든 소음의 합은 박자 순서대로 $1 + 1/2 + 1 + 1/2 + 1/3 = 10/3$이 된다.