Suppose, I have a set of mulltisets $S = \{ X_1, \cdots, X_i, \cdots, X_K\}, X_i \subset \mathbb{R}$ and need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. It is rather hard, so I want to prove it's hard. Denote $K(X) = \cup_{I \in X} I$, 
$E(X) := \sum_{i \in K(X)} |i - \textbf{median}(K(X))|$. And $|.|$ is the absolute value. $X_i$ might contains duplicated element and in $K(X)$, the union of multiset is defined as concatinating. $ \exists X_i,X_j \in S, i\neq j, X_i \cap X_j \neq \emptyset$.

But I don't have a very straightforward way to prove it's NP-complete. 
What I did instead was assuming given extra information, suppose I know the median of both $K(L^*)$ and $K(R^*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete.

Can I conclude the original problem is at least NP-complete?