Let us represent the square of the sum when the dice to buy are fixed. For the simplicity of the indices, suppose that we buy from Dice \(1\) through \(K\).

Here, we introduce the probability generating function \(f_i(x) =\frac{1}{6}(\sum_{j=1}^{6} x^{A_{i,j} }) \). Also, let \(F(x) \coloneqq \prod_{i=1}^K f_i(x)\), then the probability that the sum is \(k\) is obtained by \([x^k]F(x)\).

How can we find the expected value of the square? It is equal to \(G(1)\) where \(G(x) \coloneqq (x F'(x))'\).

Let us find \(G(1)\) using the derivative rule of the product. Let \(A_i = f_i'(1), B_i = f_i''(1)\), then

\[G(1) = \sum_{i=1}^K A_i +2 \sum_{i =1}^{K-1}\sum_{j=i+1}^{K} A_i A_j + \sum_{i=1}^K B_i,\]

so we have

\[G(1) = \sum_{i=1}^K A_i +\big( \sum_{i=1}^K A_i\big) ^ 2 - \sum_{i=1}^K A_i^2 + \sum_{i=1}^K B_i,\]

thus we obtain

\[G(1) = \big( \sum_{i=1}^K A_i\big) ^ 2+ \sum_{i=1}^K (A_i + B_i - A_i ^2) \]

By the observation above, the problem can be rephrased as follows, where \(x_i = A_i, y_i = A_i + B_i - A_i ^2 - C_i \):

---

Given are \(N\) vectors \((x_i,y_i)\). Choose exactly \(K\) vectors from them that maximizes \((\sum x) ^ 2 + \sum y \).

---

The problem can be solved by the following procedure:

What is the structure of the optimal solution? We can see that, for the optimal solution, there exists a real number \(c\) such that, for any pair of chosen and not chosen vectors \((x_i, y_i)\) and \((x_j, y_j)\), it holds that \(cx_i + y_i \geq cx_j + y_j\). Roughly speaking, the chosen \(K\) vectors are those with the largest \(cx+y\).

---

Supplement

Consider a segment \(PQ\) on a plane. When a point \(R\) move on the segment at a constant speed, (x coordinate)^2 + (y coordinate)^2 are a concave parabola, so it takes the maximum value at either endpoint. Due to this property, in general, when a set of points on a plane is given, \(x^2+y\) is maximized at one of the vertex of the convex hull of the point set.

Consider the sum vector of each combination of \(K\) vectors chosen from the \(N\) vectors, and plot those \(\binom{N}{K}\) points corresponding to the vectors on a plane. It is sufficient to enumerate the vertices of the convex hull of the point set. Since every vertex of the (upper) convex hull maximizes \(cx+y\) for some real number \(c\), so consider how we can find the point that maximizes \(cx+y\) from the \(\binom{N}{K}\) for each fixed \(c\); then we can see that the chosen \(K\) vectors are those with the largest \(cx+y\).

---

Also, the candidates of \(c\) are limited to the slope of the line passing through two points \((x_i,y_i)\) and \((x_j,y_j)\).

Since there are \(O(N^2)\) lines, and for a fixed \(c\) we can take greedily in a total of \(O(N \log N)\) time, but this is difficult to fit in the time limit.

Let us improve this solution to \(O(N^2\log N)\) using azimuth sort.

Sort the vectors in the decreasing order of the \(x\) coordinates. Also, find the sums of \(K\) largest \(x\)’s and \(y\)’s.

Sort the \(O(N^2)\) lines by the azimuth and inspect them in order. For each line, swap the two points that passes through the \(2\) points and update the top \(K\) sum of \(x\)’s and \(y\)’s appropriately.

With this trick, the time complexity is reduced to \(O(N^2\log N)\), which is fast enough.