I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$.  I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \in X} I$, then
$E(X) := \sum_{i \in K(X)} |i - \text{median}(K(X))|$, where $|.|$ is the absolute value. $X_i$ might contains duplicated elements and all operations are on multisets; in $K(X)$, $\cup$ is a union of multisets, and in $E(X)$, $\sum$ adds "with repetition" (repeated elements are summed multiple times).

I want to prove this problem is hard, 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?

---
For the sake of sharing, a wrong attempt I did on proving NP-completeness of with extra information problem. 

I was converting this "given $m_L = \textbf{median}(L), m_R = \textbf{median}(R)$ and $S$, find $L$ and $R$" problem into a integer programming feasibility problem. Thanks to [D.W][1] helped me, I should do the opposite. Maybe doing the opposite is also possible. So sharing my effort in case it helps. 

We can collect two vectors $A, B$ with length $K$, for every $X_i \in S$, get the imbalance with respect to $m_L$ and $m_R$. Namely $A[i] = \sum_{j \in X_i} sign(m_L - j) $, $B[i] = \sum_{j \in X_i} sign(m_R - j) $, where $$\text{sign}(x) = \begin{cases}
1 &\text{if }x>0\\
0 &\text{if }x=0\\
-1 &\text{if }x<0
\end{cases}$$

Now we can introduce another boolean indicator vector $I = \{0, 1\}^K$. When $I[i] = 0$, we assign $X_i$ to $L$, if $I[i] = 1$, we assigns $X_i$ to $R$.

$$
\langle I, A \rangle = 0 \\
\langle 1-I, B \rangle = 0
$$
Since $m_l$ is the median of $L$, we would definitely have the sum of imbalance equals to 0. The same applies to $m_R$.

And clearly, the newly formed problem is an integer programming problem. Which is well-known NP-complete.  Whether if it is possible to convert any such type of problem into our set partition problem in polynomial time, I still need some help 


  [1]: https://cs.stackexchange.com/users/755/d-w