Solved by binary search


#1

I solved it by doing binary seach for each row. NlogM is the complexity.