class Solution {
public:
    int NoOfSmallerElementsThanMid(vector<vector<int>>& matrix,int mid){
        int count=0;
        int n = matrix.size();
        int m = matrix[0].size();
        for(int i=0;i<n;i++){
            for(int j=m-1;j>=0;j--){
                if(matrix[i][j]<=mid){
                    count+=(j+1);
                    break;
                }
            }
        }
        return count;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int m = matrix[0].size();
        int high = matrix[n-1][m-1];
        int low = matrix[0][0];
        while(low<high){
            int mid = (low+high)>>1;
            int count = NoOfSmallerElementsThanMid(matrix,mid);
            if(count>=k){
                high = mid;
            }else{
                low = mid+1;
            }
        }
        return low;
    }
};