Kth Smallest Element in a Sorted Matrix

Given an N×N matrix where every row and every column is sorted in ascending order, your task is to find the kth smallest element in the matrix. Formally, if the matrix is denoted by \(A\) then all rows and columns satisfy \(A[i][j] \leq A[i][j+1]\) and \(A[i][j] \leq A[i+1][j]\) for all valid indices.

Input: The input begins with an integer N representing the size of the matrix. The next N lines each contain N space-separated integers describing the matrix. The final line contains the integer k.

Output: Output a single integer which is the kth smallest element in the given matrix.

It is guaranteed that the matrix is sorted as described, and that \(1 \leq k \leq N^2\).

Note: An efficient solution is expected so that the problem can be solved within a reasonable time limit. A common approach involves using a min-heap to extract the smallest elements one by one.

inputFormat

The first line contains an integer N representing the number of rows (and columns) in the matrix.

The following N lines each contain N integers separated by spaces, representing the rows of the matrix.

The last line contains an integer k.

Example:

3
1 5 9
10 11 13
12 13 15
8

outputFormat

Output a single integer which is the kth smallest element in the sorted matrix.

Example:

13

## sample

3
1 5 9
10 11 13
12 13 15
8

13