public List<int[]> kSmallestPairs(int[] a1, int[] a2, int k) {
        List<int[]> res = new ArrayList<>();
        if (a1.length == 0 || a2.length == 0) return res;
        int m = a1.length, n = a2.length;

        PriorityQueue<Pair> q = new PriorityQueue<Pair>((p1, p2) -> p1.sum - p2.sum);
        for (int i = 0; i < k && i < n; ++i) q.offer(new Pair(0, i, a1[0] + a2[i]));

        while (!q.isEmpty() && res.size() < k) {
            Pair p = q.poll();
            res.add(new int[] {a1[p.i], a2[p.j]});
            // At (i,j), no need to add both (i+1,j) and (i,j+1) which leads to duplication,
            // just add (i+1,j) since (i,j+1) will be covered by (i-1,j+1).
            if (p.i < m - 1) {
                q.offer(new Pair(p.i + 1, p.j, a1[p.i + 1] + a2[p.j]));
            }
        }
        return res;
    }