<p>You are given an <code>m x n</code> matrix <code>mat</code> that has its rows sorted in non-decreasing order and an integer <code>k</code>.</p>

<p>You are allowed to choose <strong>exactly one element</strong> from each row to form an array.</p>

<p>Return <em>the </em><code>k<sup>th</sup></code><em> smallest array sum among all possible arrays</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> mat = [[1,3,11],[2,4,6]], k = 5
<strong>Output:</strong> 7
<strong>Explanation:</strong> Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> mat = [[1,3,11],[2,4,6]], k = 9
<strong>Output:</strong> 17
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
<strong>Output:</strong> 9
<strong>Explanation:</strong> Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.  
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == mat.length</code></li>
	<li><code>n == mat.length[i]</code></li>
	<li><code>1 &lt;= m, n &lt;= 40</code></li>
	<li><code>1 &lt;= mat[i][j] &lt;= 5000</code></li>
	<li><code>1 &lt;= k &lt;= min(200, n<sup>m</sup>)</code></li>
	<li><code>mat[i]</code> is a non-decreasing array.</li>
</ul>

class Solution {
public:
// Structure to represent an element in the priority queue
struct Element {
    vector<int> indices;  // Indices of selected elements from each row
    int sum;              // Sum of selected elements

    Element(vector<int> idx, int s) : indices(idx), sum(s) {}

    // Comparison operator for min-heap
    bool operator>(const Element& other) const {
        return sum > other.sum;
    }
};

// Function to find the k-th smallest sum
int kthSmallest(vector<vector<int>>& mat, int k) {
    int n = mat.size();
    priority_queue<Element, vector<Element>, greater<Element>> minHeap;

    // Initialize with the first elements
    vector<int> initialIndices(n, 0);
    int initialSum = 0;
    for (int i = 0; i < n; ++i) {
        initialSum += mat[i][0];
    }
    minHeap.push(Element(initialIndices, initialSum));

    // Set to keep track of visited index combinations
    set<vector<int>> visited;
    visited.insert(initialIndices);

    while (!minHeap.empty() && k > 0) {
        // Extract the minimum sum element
        Element current = minHeap.top();
        minHeap.pop();
        --k;

        // If this is the k-th smallest sum, return it
        if (k == 0) {
            return current.sum;
        }

        // Generate next possible sums
        for (int i = 0; i < n; ++i) {
            if (current.indices[i] + 1 < mat[i].size()) {
                vector<int> nextIndices = current.indices;
                nextIndices[i]++;

                // Check if this combination of indices has been visited
                if (visited.find(nextIndices) == visited.end()) {
                    int nextSum = current.sum - mat[i][current.indices[i]] + mat[i][nextIndices[i]];
                    minHeap.push(Element(nextIndices, nextSum));
                    visited.insert(nextIndices);
                }
            }
        }
    }

    return -1; // In case k is out of range
}
};
65483