Matrix Search

Given a two-dimensional integer matrix, where every row and column is sorted in ascending order, find the kth (0-indexed) smallest number.

Constraints

• n, m ≤ 250 where n and m are the number of rows and columns in matrix

https://binarysearch.com/problems/Matrix-Search

Examples

Example 1

Input

• matrix =

[[ 1, 3,30],
 [ 2, 3,31],
 [ 5, 5,32]]

• k = 4

Output

• answer = 5

Example 2

Input

• matrix =

[[1,2,3]]

• k = 0

Output

• answer = 1

Example 3

Input

• matrix =

[[1],
 [2],
 [3]]

• k = 2

Output

• answer = 3

Solution