도박 문제 전문 상담은 국번없이 1336

2024년 3월 9일 제4회 MatKor Cup이 개최된다. 이번 MatKor Cup에는 총 $n$명이 참가했고, 각 참가자는 $1$번부터 $n$번까지의 번호가 붙어있다.

이번 대회 운영진인 준혁이는 어떤 참가자가 우승할 지에 대해 자신을 제외한 운영진끼리 베팅을 하도록 했다. 베팅 결과 ‘$i$번 참가자가 우승한다’에 $a\_i$원의 금액이 걸렸고, 총 $s=a\_1+a\_2+\cdots +a\_n\ne 0$원의 금액이 걸렸다. 실제로 $i$번째 사람이 우승할 확률은 베팅 금액에 비례하는 $\frac{a\_i}{s}$이다. 우승자는 반드시 한 명이다.

도박을 싫어해 베팅에 참여하지 않은 종우는 자신이 공평하게 배당을 나눌 수 있다고 말했다. 그 결과, 종우가 배당을 정하기로 했다.

$i$번 참가자의 배당이 $b\_i$라고 할 때, 배당 상수 $m$과 $t$에 대해 배당의 총합이 $t=b\_1^m+b\_2^m+\cdots +b\_n^m$가 되도록 $b\_i$들을 정하고자 한다. 이때 두 배당 상수는 양의 정수이고, 각 참가자의 배당은 음이 아닌 실수이다.

만약 $k$번 참가자가 우승한다면, 준혁이는 $k$번 참가자에 베팅한 사람들이 건 돈의 $b\_k$배를 각각 배당금으로 지급한다. 즉, $k$번 참가자가 우승할 경우 받은 $s$원에서 $a\_kb\_k$원을 배당금으로 지급하므로, 초기에 비해 $s-a\_kb\_k$원을 벌게 된다. 만약 이 값이 음수라면, 그 절댓값만큼의 돈을 잃게 된다.

종우는 준혁이가 도박 운영을 통해 돈을 버는 것을 못마땅하게 생각해 준혁이가 최대한 돈을 벌지 못하게 하고 싶다. 참가자별로 걸린 금액과 배당 상수가 주어질 때 종우를 도와 준혁이가 버는 금액의 기댓값이 최소가 되도록 배당을 조정해 보자.

첫 번째 줄에 대회 참가자의 수 $n$, 배당의 총합을 결정할 정수 상수 $m$, $t$가 공백으로 구분되어 주어진다. $(1\le n, m, t\le 10^6)$

두 번째 줄에 베팅 결과 각 참가자에게 걸린 금액을 나타내는 $n$개의 정수 $a\_i$가 공백으로 구분되어 주어진다. $(0\le a\_i\le 1\\,000)$

주어지는 입력은 $s> 0$을 만족한다.

준혁이가 버는 금액의 기댓값의 최솟값을 출력한다. 이 값이 음수일 수 있음에 유의하자.

정답과의 절대오차 또는 상대오차가 $10^{-6}$ 이하이면 정답으로 인정된다.