I solved it using sorting + dp. In tags it is 'binary search' + 'sorting'. Couldn't think of binary search solution.

BTW, size limit is 10^6 and not 10^5.