We want a solution around \(O(N^3)\), maybe \(O(N^3M)\) with a good constant factor given the runtime constraints.

Define \(D = \frac{U-L}{2}\) and \(X = \frac{L+U}{2}\). Note that the standard deviation of the uniform distribution \(\mathcal{U}(L, U)\) is approximately \(\frac{D}{\sqrt{3}}\).

Now, generate \(A\) as follows: pick \(N\) random integers generated from the distribution \(\mathcal{N}(\frac{X}{6}, \frac{D}{\sqrt{18}})\), where \(\mathcal{N}\) denotes the normal distribution. The motivation here is that summing up \(6\) random numbers from \(A\) gives \(\mathcal{N}(X, \frac{D}{\sqrt{3}})\) where \(\frac{D}{\sqrt{3}}\) is the standard deviation of the uniform distribution \(\mathcal{U}(L, U)\) as above.

Now, go through \(B\). For each \(B_i\), greedily find the \(6\) numbers in \(A\) that have not been removed that sum closest to \(B_i\), and remove them from \(A\), and those are the \(6\) numbers associated with the partition \(B_i\). We can get an approximate answer of which \(6\) numbers sum closest to \(B\) using Meet in the Middle: split the list of numbers in \(A\) that have not been used in half, then for each half we calculate all possible sums of \(3\) numbers in that half. We can then sort the lists of sums and using two pointers to figure out what sums closest to \(B_i\).

If we can sort in \(O(N)\) time (ie with Radix sort) this runs in about \(O(\binom{N/2}{3} + \binom{N/2-3}{3} + ... + \binom{N/2-3(M-1)}{3}) = O(N^3M)\) time, where \(\binom{N/2}{3} + \binom{N/2-3}{3} + ... + \binom{N/2-3(M-1)}{3})\) is actually about 157 million, and this would score about 131 to 132 billion. However, I was unable to get this to run fast enough, so I instead considered up to \(240\) random numbers in \(A\) that have not been used in each step (or all the remaining unused numbers in \(A\) if the number of unused numbers in \(A\) is less than \(240\)) and ran a Meet in the Middle Algorithm with that shortened list, for about 125 billion points.