Find the kth Smallest Element in a Sorted Matrix

You are given a 2D matrix in which each row and each column is sorted in non-decreasing order. Your task is to find the \(k^{th}\) smallest element in the matrix. The element order is defined by the sorted order of all elements in the matrix.

Input Format: The first line contains two integers \(n\) and \(m\) which represent the number of rows and columns respectively. This is followed by \(n\) lines, each containing \(m\) space-separated integers that form the matrix. The last line of input contains an integer \(k\), which is the order statistic to be found.

Note: The matrix is sorted both row-wise and column-wise. You may use \(O(k)\) or \(O(n\log k)\) algorithms to solve this problem efficiently.

inputFormat

The input is read from stdin in the following format:

1. The first line contains two integers \(n\) and \(m\): the dimensions of the matrix.
2. The next \(n\) lines each contain \(m\) space-separated integers representing the rows of the matrix.
3. The last line contains an integer \(k\), representing which smallest element to find.

outputFormat

Output the \(k^{th}\) smallest element from the matrix to stdout.

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

13