We have ~N~ regions of a target (~1~ circle surrounded by ~N-1~ rings) and ~M~ coordinates. We want to assign ~N~ given point values to the ~N~ regions such that the total score is minimized (and then again so it's maximized). The score is defined as the sum of the products of each ring's score with the number of shots that land in each ring. Formally, the problem asks to find the minimum and maximum possible cross products between the hit-counts of each ring and the point value we assign to each ring. By definition, the cross-product of two size ~N~ arrays ~A~ and ~B~ is equal to the sum ~A[1] \times B[1] + A[2] \times B[2] + \dots + A[N] \times B[N]~.

By the simple equation of a circle centered at the origin, we know that a shot ~i~ lands in ring ~j~ iff ~\sqrt{X_i^2+Y_i^2}~ is strictly less than or equal to the outer radius ~R_j~, and strictly greater than ~R_{j-1}~ (if ~j > 1~). To avoid any possible precision issues with floating point numbers (in cases where a shot lands very close to the border of a ring), this process can be handled entirely using (64-bit) integers, by comparing squared distances instead (for example, comparing ~X^2+Y^2~ against ~R^2~). The hit counts can be precomputed naïvely by looping through each of the ~M~ rings, and then counting how many of the ~N~ darts land in the ring using the formula above. This will have a running time of ~\mathcal O(NM)~. Then, we can try naïvely permuting all ~N!~ orderings of ~P~ and assign them to each ring, and then for each permutation computing the cross product of the current permutation and the hit-counts of each ring. Doing this should pass the first subtask in ~\mathcal O(NM + N!) = \mathcal O(N!)~ time (since ~N \le 10~, so ~N! \le 10! = 3\,628\,800~), and is thus given 6/40 points.

Suppose we already have the hit-counts for each ring. Now intuitively, in order to maximize Bond's score, we should assign the largest ~P~ values to the rings which are hit by the largest number of shots, and the smallest ~P~ values to those which are hit the least (and vice versa to minimize his score). This is as easy as sorting ~P~ and the counts in increasing order, calculating the cross-product (for the maximum), then reversing ~P~ and calculating the cross-products again (for the minimum). Since each sort takes ~N \log N~, we've reduced the time complexity to ~\mathcal O(N \log N + NM) = \mathcal O(NM)~. This is sufficient to pass all but the last set of cases, obtaining 17/35 points. However, to get full marks, we must handle the bottleneck of computing the hit-counts efficiently.

If we just consider the rings in terms of their distances, then we actually just get a sorted array of integers. To find where a point lands, we want to find the first ~R~ value which is not less than the distance of the shot from the origin. Since the distances are sorted, we can use binary search in ~\mathcal O(\log N)~ time to pinpoint the exact position where it lands. Across ~M~ shots, the time complexity will be ~\mathcal O(M \log N)~. So, the overall solution will run in ~\mathcal O(M \log N + N \log N)~.