<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:
    # To solve the problem of finding the k-th smallest sum of a matrix with sorted rows, 
    # we can use a min-heap (priority queue). The idea is to incrementally build sums from the smallest possible combinations of elements from each row 
    # and use a min-heap to keep track of the smallest sums encountered so far. We will pop the smallest sum from the heap and push new sums by adding the next element in one of the rows, 
    # continuing this process until we reach the k-th smallest sum.
    def kthSmallest(self, mat: List[List[int]], k: int) -> int:
        
        #keeping track of smallest sum by take first element of each row
        # it will contain sum + indices of both rows from where we form the sum
            m = len(mat)
            n = len(mat[0])

            # Initialize the heap with the smallest sum (taking the first element from each row)
            min_heap = [(sum(row[0] for row in mat), [0] * m)]
            
            # Initialize the visited set with the starting indices combination
            visited = set()
            visited.add(tuple([0] * m))
            
            while k > 0:
                curr_sum, curr_indices = heapq.heappop(min_heap)
                k -= 1
                
                if k == 0:
                    return curr_sum
                
                for i in range(m):
                    if curr_indices[i] + 1 < n:
                        new_indices = curr_indices[:]
                        new_indices[i] += 1
                        
                        # Convert the new indices list to a tuple to check if it has been visited
                        new_tuple = tuple(new_indices)
                        
                        if new_tuple not in visited:
                            visited.add(new_tuple)
                            new_sum = curr_sum - mat[i][curr_indices[i]] + mat[i][new_indices[i]]
                            heapq.heappush(min_heap, (new_sum, new_indices))




        
129