Kth Smallest Element in a Sorted Matrix

You are given an n x n matrix of integers where each row and each column is sorted in non-decreasing order. Your task is to find the kth smallest element in the matrix.

The matrix satisfies the following ordering property:

[ \text{matrix}[i][j] \leq \text{matrix}[i][j+1] \quad \text{and} \quad \text{matrix}[i][j] \leq \text{matrix}[i+1][j] ]

Input/Output format: See details below.

Example:

Input:
3 8
1 5 9
10 11 13
12 13 15
Output:
13

</p>

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers n and k, where n is the dimension of the square matrix and k is the order of the smallest element you need to find.
• Each of the next n lines contains n space-separated integers representing a row of the matrix.

It is guaranteed that the matrix is sorted in non-decreasing order both row-wise and column-wise.

outputFormat

Output the kth smallest element in the matrix to stdout.

## sample

3 8
1 5 9
10 11 13
12 13 15

13