Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

Example 1:

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

Example 2:

Input:
1
-5
1
Output: -5

Constraints:

• 1 ≤ n ≤ 300
• -10⁹ ≤ matrix[i][j] ≤ 10⁹
• 1 ≤ k ≤ n²

Input format: First line: n. Next n lines: n integers. Last line: k.

Output format: The kth smallest value.