Notice that the average of weights of lucky bags \(\bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D)=\frac{1}{D}(W_1+W_2+\cdots+W_N)\) are independent of how to divide items.
Here we denote the \(i\)-th item simply by item \(i\).

We consider solving this problem using dynamic programming.
For a subset \(S\) of \(\{1,2,\ldots,N\}\) and an integer \(k\) such that \(1\leq k \leq D\), let \(dp[S][k]\) be the minimum possible \(\displaystyle\sum_{i=1}^k (y_i-\bar{x})^2\) where \(y_1,y_2,\ldots,y_k\) are the weights of lucky bugs, when the items \(g\in S\) are distributed to \(k\) bags. Here, notice that \(\bar{x}\) is the constant uniquely determined by the input, as mentioned above, and is independent of \(S\) and \(k\). The final answer is obtained by dividing \(dp[\{1,2,\ldots,N\}][D]\) by \(D\).

First, regarding \(dp[S][1]\), if there is one bag the only way is to put all the items in the set into the bag, so the sought value is \(\left(\left(\displaystyle\sum_{g\in S}W_g\right)-\bar{x}\right)^2\).
Then, for \(2\leq k\leq D\), let us consider how to find \(dp[S][k]\), assuming that \(dp[S'][k’]\) are already known for all sets \(S'\subset \{1,2,\ldots,N\}\) and positive integers \(dp[S][k]\). Fixing one bag, considering which items to put into it, and taking the minimum of it, this value can be obtained as

\[ dp[S][k]=\min_{T\subseteq S} (dp[(S-T)][k-1]+dp[T][1]). \]

Here, \((S-T)\) denotes the different of set, \((S-T)=(S\backslash T)=\{x|x\in S \land x\notin T\}\). By repeating this for each \(k=2,3,\ldots,D\) in order, the final answer can be obtained.

Now we estimate the complexity. The value \(dp[S][1]\) can be obtained in \(O(N)\) time for each \(S\), for a total complexity of \(O(N2^N)\), which is OK.

Denoting the size of a set \(S\) by \(\lvert S\rvert\), there are \(2^{\lvert S\rvert}\) candidates of sets \(T\subseteq S\). Thus, for a specific \(S\) and \(2\leq k\leq D\), one can evaluate \(dp[S][k]\) from \(dp[S'][k’]\) \((S'\subset \{1,2,\ldots,N\}, k'\leq k-1)\) with \(2^{|S|}\) operations, regardless of \(k\). Since there are \({}_NC_s\) subsets of \( \{1,2,\ldots,N\}\) of size \(s\), noticing the range of \(k\), the overall number of operations is expressed as

\[ \left(\displaystyle\sum_{s=0}^N {}_NC_s\times 2^s \right)\times (D-1) =(2+1)^N\times(D-1)< 3^N\times D. \]

When \(D\leq N\leq 15\), we have \(3^N\times D\leq 2.2\times 10^8\), and each operation is simple addition and comparisons, so it easily fits in the time limit.
Thus, the problem can be solved.

The following are caveats in implementation.

• It is basically bad idea to store sets using indices; the recommended way is to represent a set as a sequence of bits, expressing which elements are contained.
• When a set is represented as a bit sequence, the subsets of the set corresponding to the bit sequence \(x\) can be enumerated by starting from \(y=x\) and repeatedly replacing \(y\) with \( (y-1)\& x\) until \(y=0\). (The variable \(y\) spans over bit sequences corresponding to all subsets of \(x\).) Here, \(\&\) denotes the logical product. We omit the proof here.
• Beware of how many digits to print. For example, if you print only six digits or less, the error may cause WA (Wrong Answer) verdict.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n,d,x;
	long double w[15];
	long double ave=0;
	long double dp[(1<<15)][16];
	long double y;

	cin>>n>>d;
	for(int i=0;i<n;i++)cin>>w[i],ave+=w[i];
	ave/=((long double)d);
	for(int i=0;i<(1<<n);i++){
		y=0;
		for(int j=0;j<n;j++){
			if(i&(1<<j))y+=w[j];
		}
		dp[i][1]=pow(y-ave,2);
		for(int j=2;j<=d;j++){
			dp[i][j]=dp[i][j-1]+dp[0][1];
			x=i;
			while(x>0){
				dp[i][j]=min(dp[i][j],dp[i-x][j-1]+dp[x][1]);
				x=(x-1)&i;
			}
		}
	}
	cout<< setprecision(10) <<(dp[(1<<n)-1][d]/((long double)d))<<endl;
	return 0;
}