Find K-th Smallest Element in a Sorted Matrix

You are given a matrix \( A \) of size \( m \times n \) where each row is sorted in non-decreasing order. Your task is to find the \( k \)-th smallest element in the matrix.

Input Format: The first line contains three integers \( m \), \( n \) and \( k \). Each of the next \( m \) lines contains \( n \) integers representing the rows of the matrix.

Output Format: Output a single integer, the \( k \)-th smallest element in the matrix.

Note that the matrix does not necessarily have distinct elements.

inputFormat

The input is read from standard input with the following format:

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

Where \( m \) is the number of rows, \( n \) is the number of columns, and \( k \) specifies which smallest element to find.

outputFormat

Output to standard output a single line containing the \( k \)-th smallest element from the matrix.

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

13