/**
knakul853
**/

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {

       int n = (int)matrix[0].size();
        int m = (int)matrix[0].size();

        priority_queue<int, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>>pq;

        for(int i=0;i<n;i++)
        {
            pq.push({matrix[i][0],{i, 0}});
        }
        int ans = 0;

        while(k--)
        {
            auto node = pq.top();
            int j = node.second.second;
            int i = node.second.first;
            ans = node.first;
            pq.pop();

            if(j+1<m)
            {
                pq.push({matrix[i][j+1], {i, j+1}});
            }
        }

        return ans;
    }
};