A complicated variant of Weighted Median problem
A tip: this problem becomes much easier if you sort the $x$'s into increasing order.  (If you sort by the $w$'s, your life will be much much harder.)

More precisely, you should sort the entries so the $x$-values are in increasing order, resolving ties so the $w$-values are in increasing order.  This amounts to lexicographic order on $(x,w)$.  This way, if $i&lt;j$, then $x_i\le x_j$ and either $x_i&lt;x_j$ or $w_i\le w_j$.



Once the elements are sorted in this way, you can solve this problem with a linear scan.

Just scan from left to right (i.e., from $i=1$ to $n$), keeping track of the sum of the weights seen so far (i.e., $w_1+w_2+\dots+w_i$).  When this sum transitions from less than $1/2$ to greater than $1/2$, you've found the weighted median.  At the very end, if there are multiple elements with the same $x$-value as the one you found, scan leftwards to find the first element with the same $x$-value as the one you initially found.

Running time: $O(n \lg n)$.  It takes $O(n \lg n)$ time to sort, plus $O(n)$ time for the linear scan.  No need for fancy dynamic programming.



My thanks to Dukeling for helpful comments and corrections!