find separate pairs of points with minimal total distance
Sort the items so that $s_1 \le s_2 \le \dots \le s_{N_S}$. Then: 


If $N_S$ is even, assign all the odd-numbered items to $A$, all even-numbered items to $B$, and pair the first item of $A$ with the first of $B$, etc. This assignment must be optimal, since any pairing in which two pairs overlap can always be transformed into a pairing with no overlap that does not cost more. 
If $N_S$ is odd, enumerate over all possible items $s_i$ in $S$ and for each of them, compute the best partition of $S \setminus \{s_i\}$, which is an even-size set, using the previous case. Return the best partition among all $N_S$ cases. 


The total cost of this procedure is $O(N_S \log N_S)$ when $N_S$ is even and $O(N_S^2 \log N_S)$ when $N_S$ is odd.