Given a row-wise sorted matrix of size M × N, write a program to find the median of the matrix given.

Problem Note

  • It is assumed that M × N is always odd.
  • No extra memory is allowed.

Example 1

Input:
 [   
   [1, 3, 5],   
   [2, 6, 9],  
   [3, 6, 9] 
]
Output: 5 
Explanation: If we put all the values in a sorted array A[] = [1, 2, 3, 3, 5, 6, 6, 9, 9], Here Median is 5.