K-й наименьший элемент в отсортированной матрице

Дана матрица matrix размера n x n, каждая строка и каждый столбец отсортированы по возрастанию. Верните k-й по величине элемент среди всех n*n (1-индексация). Полная сортировка всех элементов работает, но подумайте про бинарный поиск по ЗНАЧЕНИЮ ответа: для любого числа x можно за O(n) посчитать, сколько элементов матрицы не превышает x, двигаясь лесенкой от левого нижнего угла.