Cellular Network

A cellular network is a radio network made up of cells, each served by a base station in the cell. The base station receives call signals from the mobile users in its cell and connects those calls to the wired land-line telephone network. To route an incoming call to a mobile, the network must know which cell the mobile is currently in.

Mobiles move from cell to cell. If a mobile reported every boundary crossing, the network would always know its exact cell and paging (finding the mobile) would be trivial. In practice this is infeasible because radio bandwidth is limited, so when a call arrives the network knows only a limited set of cells the mobile might be in. Many paging strategies exist to locate a mobile efficiently; the goal is to minimize both the delay and the cost of paging until the mobile is found.

Formally, the location area is a set of $n$ cells $C = \{c_1, c_2, \dots, c_n\}$, and the mobile is guaranteed to be in exactly one of them when a call arrives. In one paging round (one unit of time) the network can page any subset of these cells and learn whether the mobile is among the paged cells. Paging all $n$ cells in a single round is the fastest strategy but uses a lot of bandwidth.

The network can often estimate the mobile's whereabouts as $n$ independent probabilities: let $p_i$ be the probability that the mobile is in cell $c_i$. A sequential paging strategy pages the cells one per round and stops as soon as the mobile is found. Its average cost (number of cells paged) $\bar{C}$ and average delay (number of rounds) $\bar{D}$ are:

$\bar{C} = \sum_{i=1}^{n} (i \times p_i), \qquad \bar{D} = \sum_{i=1}^{n} (i \times p_i).$

A parallel paging strategy pages several cells simultaneously. Sequential paging has a lower cost than parallel paging but a larger delay. Parallel paging partitions the location area into an ordered series of groups called paging zones. Let $Z_1, Z_2, \dots, Z_w$ be a partition of $C$ into $w$ non-empty zones. When a call arrives, all cells of $Z_1$ are paged in the first round; if the mobile is not found, all cells of $Z_2$ are paged in the second round, and so on. Let $n_i = |Z_i|$ and let the zone probability be $\pi_i = \sum_{c_j \in Z_i} p_j$. Then:

$\bar{C} = \sum_{i=1}^{w} \left(\sum_{j=1}^{i} n_j\right) \pi_i, \qquad \bar{D} = \sum_{i=1}^{w} (i \times \pi_i).$

Parallel paging trades bandwidth for time: increasing the number of zones tends to lower the cost, while decreasing it tends to raise the cost. Even for a fixed number $w$ of zones, the cost depends on how the cells are partitioned.

For example, take $n = 5$ cells with these probabilities:

Partitioning into $Z_1 = \{c_1, c_2, c_3\}$ and $Z_2 = \{c_4, c_5\}$ gives:

• $\bar{C} = n_1\pi_1 + (n_1 + n_2)\pi_2 = 3(0.3 + 0.05 + 0.1) + (3 + 2)(0.3 + 0.25) = 3 \times 0.45 + 5 \times 0.55 = 4.1$
• $\bar{D} = 1 \times \pi_1 + 2 \times \pi_2 = 1(0.45) + 2(0.55) = 1.55$

Partitioning into $Z_1 = \{c_1, c_4\}$ and $Z_2 = \{c_2, c_3, c_5\}$ gives:

• $\bar{C} = n_1\pi_1 + (n_1 + n_2)\pi_2 = 2(0.3 + 0.3) + (3 + 2)(0.05 + 0.1 + 0.25) = 2 \times 0.6 + 5 \times 0.4 = 3.2$
• $\bar{D} = 1 \times \pi_1 + 2 \times \pi_2 = 1(0.6) + 2(0.4) = 1.4$

Given the number of cells, each cell's probability, and a fixed number $w$ of paging zones, partition the cells into $w$ zones so that the average paging cost $\bar{C}$ is minimized.

The input begins with a line containing the number of test cases $T$. Each test case consists of two lines. The first line contains two integers $n$ and $w$: the number of cells in the location area and the number of paging zones, with $1 \le w \le n \le 100$. The second line contains $n$ integers $u_1, u_2, \dots, u_n$; the probability of cell $c_i$ is $p_i = u_i / (u_1 + u_2 + \dots + u_n)$. Every $u_i$ is between 1 and 10000.

For each test case, print exactly one line containing the minimum average paging cost needed to locate the mobile, rounded to exactly 4 digits after the decimal point (round half up).