A monitoring grid stores readings in a matrix with R rows and C columns. Every row is sorted in non-decreasing order from left to right, and every column is sorted in non-decreasing order from top to bottom. Values may repeat.
Given k (1-indexed), print the k-th smallest value among all R * C cells, counting repeated values with multiplicity (so if the two smallest cells are both 3, the 1st and 2nd smallest are both 3).
Input format
Line 1: two integers R and C.
Next R lines: each has C space-separated integers, a row of the matrix.
Last line: an integer k.
Output format
A single integer: the k-th smallest value in the matrix.
Constraints
- 1 <= R, C <= 1000
- 1 <= k <= R * C
- -1000000000 <= each value <= 1000000000
- Each row and each column is sorted in non-decreasing order.