class Solution {

    static class Pair implements Comparable<Pair>{

        int i;
        int val;
        public Pair(int i, int val) {
            this.i=i;
            this.val=val;
        }

        @Override
        public int compareTo(Pair x) {
            return this.val-x.val;
        }

    }
    public int kthSmallest(int[][] a, int k) {
        int n = a.length;
        int m = a[0].length;
        ArrayList<Integer> A = new ArrayList<>();
        int[] p = new int[n];
        PriorityQueue<Pair> PQ = new PriorityQueue<>();
        for(int i=0;i<n;i++) {
            PQ.add(new Pair(i,a[i][0]));

        }

        while(A.size() < k){
            Pair tmp = PQ.poll();
            A.add(tmp.val);
            p[tmp.i]++;
            if(p[tmp.i] < m) {
                PQ.add(new Pair(tmp.i, a[tmp.i][p[tmp.i]]));
            }
        }

        return A.get(k-1);
    }
}