703. Kth Smallest Element in a Sorted Matrix

0

Medium

Given an n x n matrix where each row and column is sorted in ascending order, find the kth smallest element in the matrix. The kth smallest element refers to the element that appears in the sorted order at the kth position, not necessarily a distinct element.

Input Format

The input consists of an integer n, representing the size of the matrix, followed by n*n integers denoting the elements of the matrix. Finally, an integer k is provided.

Output Format

The output is the kth smallest element in the matrix.

Example

Input

3
1 5 9
10 11 13
12 13 15
8

Output

13

Constraints

The size of the matrix, n, is equal to the length of the matrix and the length of each row in the matrix. The value of n is between 1 and 300, inclusive. The elements in the matrix are integers ranging from -10^9 to 10^9. All the rows and columns of the matrix are sorted in non-decreasing order. The value of k is between 1 and n^2, inclusive.

Loading...

View Submissions

Console