Given a row-wise sorted matrix arr 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, 4, 5],   
   [2, 6, 9],  
   [3, 6, 10] 
]
Output: 5 
Explanation: If we put all the values in a sorted array A[] = [1, 2, 3, 4, 5, 6, 6, 9, 10], Here Median is 5.