#include <vector> // 378. O(Nlog(R−L)) O(1)
using namespace std;

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k){
        int n = (int)matrix.size();
        int L = matrix[0][0], R = matrix[n - 1][n - 1];

        auto countLE = [&](int x){
            int i = n - 1, j = 0, cnt = 0;
            while (i >= 0 && j < n) {
                if(matrix[i][j] <= x){
                    cnt += i + 1;
                    ++j;
                } else{
                    --i;
                }
            }
            return cnt;
        };
        
        while (L < R){
            int m = L + (R - L) / 2;
            if (countLE(m) >= k) R = m;
            else L = m + 1;
        }
        return L;
    }
};