#include <iostream>
#include <vector>
#include <cstdint>
#include <climits>
#include <algorithm>
using namespace std;

int kthSmallestMine(vector<vector<int>>& matrix, int k) {
    int lowest=INT_MAX, highest=INT_MIN;
    for(vector<int> row: matrix) {
        lowest=min(lowest, row[0]);
        highest=max(highest, row[row.size()-1]);
    }
    
    while(lowest<highest) {
        int mid=lowest+(highest-lowest+1)/2;
        int places=0;
        
        for(int i=0; i<matrix.size(); i++) {
            places+=(upper_bound(matrix[i].begin(), matrix[i].end(), mid)-matrix[i].begin());
        }
        if(places<=k) lowest=mid;      //this gives a number _not_ in the matrix (14)
        else highest=mid-1;
        // if(places<k) lowest=mid+1;  //this gives a number _in_ the matrix (13)
        // else highest=mid;   //also use mid=lowest+(highest-lowest)/2 instead;
    }
    
    return lowest;
}

int kthSmallestTheirs(vector<vector<int>>& matrix, int k) {
    int lowest=INT_MAX, highest=INT_MIN;
    for(vector<int> row: matrix) {
        lowest=min(lowest, row[0]);
        highest=max(highest, row[row.size()-1]);
    }
    
    while(lowest<highest) {
        int mid=lowest+(highest-lowest)/2;
        int places=0;
        
        for(int i=0; i<matrix.size(); i++) {
            places+=(upper_bound(matrix[i].begin(), matrix[i].end(), mid)-matrix[i].begin());
        }
        if(places<k) lowest=mid+1;  //this gives a number _in_ the matrix (13)
        else highest=mid;   //also use mid=lowest+(highest-lowest)/2 instead;
    }
    
    return lowest;
}   
int main() {
	vector<vector<int>> v={{1,100,1000}, {10, 150, 1500}, {30, 300, 3000}};
	cout<<kthSmallestMine(v, 7)<<"\n";
	cout<<kthSmallestTheirs(v, 7);
	
	return 0;
}