int findNextGreaterIndex(int key,vector<int> &arr){

    int low=0,high=arr.size()-1,mid=0;
    while(low<high){
        mid=(low+high)/2;
        if(arr[mid]>key)
            high=mid;
        else    low=mid+1;
    }
    if(arr[low] <= key) return low+1;
    return low;
}
int calculateMedianOfMatrix(vector<vector<int> > &matrix) {

    int n=matrix.size(),m=matrix[0].size();
    int median=((n*m)+1)/2;

    map<int,int> mp;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int key=matrix[i][j],total=0;
            if(mp.find(key) != mp.end())    //already seen this key
                continue;
            for(int r=0;r<n;r++)
                total+=findNextGreaterIndex(key,matrix[r]);
            mp[key]=total;
        }
    }

    int sum=0;
    for(auto i:mp){
        if(sum!=0)
            i.second-=sum;
        sum+=i.second;

        if(sum>=median)
            return i.first;
    }

}