Optimal partition of a set of pairs
If I understood well the problem:

$S = \{ (a_1, m-a_1), (a_2, m-a_2), ..., (a_n, m-a_n),\; m&gt;2 $

$\sum_{a_i \in C} a_i &gt; \sum_{a_i \in C} (m - a_i)$ and $\sum_{a_j \in D} a_j &gt; \sum_{a_j \in D} (m - a_j)$ is equivalent to

$\sum_{a_i \in C} a_i &gt; m * |C| - \sum_{a_i \in C} a_i$ and $\sum_{a_j \in D} a_j &gt; m * |D| - \sum_{a_j \in D} a_j$  is equivalent to

$2 * \sum_{a_i \in C} a_i &gt; m * |C|$ and $2 * \sum_{a_j \in D} a_j &gt; m * |D|$  is equivalent to

$2 * \sum_{a_i \in C} a_i &gt; m * |S| / 2$ and $2 * \sum_{a_j \in D} a_j &gt; m * |S| / 2$  is equivalent to

$4 * \sum_{a_i \in C} a_i &gt; m * |S|$ and $4 * \sum_{a_j \in D} a_j &gt; m * |S|$ 

Then given an instance of the PARTITION problem $\Pi$, $S = \{ a_1, ..., a_n \}, \sum a_i = 2k$

Add two equal big integers $z &gt;&gt; k$ such that $z = t * (|S|+2) - k + 1$;
the equivalent partition problem $\Pi'$ is $S' = S \cup \{a_{n+1}=z, a_{n+2}=z\}$, $\sum = 2(k+z)$ i.e. the sum of the elements of the two equal partitions must be equal to $k+z$

Now you can set $m = 4*((k+z)-1)/|S'|$ which is an integer: $m  = 4 * ( k + t*|S'| - k + 1 - 1)/|S'| = 4 * (t - 1) * |S'|$ and your problem inequalities become: 

$\sum_{a_i \in C} a_i &gt; k+z-1$ and $\sum_{a_j \in D} a_j &gt;  k + z - 1$

And it have a solution if and only if $\Pi'$ has a solution.