K-th Smallest Element in a Sorted Matrix

You are given an \(n \times m\) matrix where every row and every column is sorted in non-decreasing order. Your task is to find the \(k\)-th smallest element in the matrix.

The matrix satisfies the following conditions:

• Each row is sorted from left to right.
• Each column is sorted from top to bottom.

Note: The \(k\)-th smallest element is defined based on the sorted order of all the elements in the matrix. For example, when \(k = 1\), the answer is the smallest element in the matrix.

For explanation, consider a matrix A of size \(n \times m\). If you flatten it into a sorted list \(L\), then the answer is \(L[k-1]\). You are encouraged to use an efficient algorithm (such as a min-heap) to handle this problem.

inputFormat

The input is given from standard input (stdin) and has the following format:

n m
A[0][0] A[0][1] ... A[0][m-1]
A[1][0] A[1][1] ... A[1][m-1]
...
A[n-1][0] A[n-1][1] ... A[n-1][m-1]
k

Where:

• \(n\) and \(m\) are the number of rows and columns respectively.
• The next \(n\) lines contain \(m\) integers each representing the elements of the matrix.
• \(k\) is the position (1-indexed) of the smallest element to be found.

outputFormat

Print a single integer representing the \(k\)-th smallest element in the matrix to standard output (stdout).

## sample

3 3
1 5 9
10 11 13
12 13 15
8

13