public class Solution {
public boolean guess(int g,int[][] matrix, int k, int n){
int sum = 0;
for(int i = 0; i < n; i++){
int L = 0;
int R = n-1;
int ans = -1;
while(L <= R){
int mid = (L + R) / 2;
if(matrix[i][mid] < g){
ans = mid;
L = mid + 1;
}else{
R = mid - 1;
}
}
sum += (ans + 1);
}
return k > sum;
}
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int L = matrix[0][0];
int R = matrix[n-1][n-1];
int ans = 0;
while(L <= R){
int mid = (int)(((long)L + R )/2);
if(guess(mid,matrix,k,n)){
ans = mid;
L = mid + 1;
}else{
R = mid - 1;
}
}
return ans;
}
}
