#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void * wmem;
char memarr[ 96000000 ] ;
template < class S, class T> inline S max_L( S a,T b) {
return a>= b? a: b;
}
template < class T> inline void walloc1d( T ** arr, int x, void ** mem = & wmem) {
static int skip[ 16 ] = { 0 , 15 , 14 , 13 , 12 , 11 , 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 } ;
( * mem) = ( void * ) ( ( ( char * ) ( * mem) ) + skip[ ( ( unsigned long long ) ( * mem) ) & 15 ] ) ;
( * arr) = ( T* ) ( * mem) ;
( * mem) = ( ( * arr) + x) ;
}
template < class T> inline void walloc1d( T ** arr, int x1, int x2, void ** mem = & wmem) {
walloc1d( arr, x2- x1, mem) ;
( * arr) - = x1;
}
template < class T1> void sortA_L( int N, T1 a[ ] , void * mem = wmem) {
sort( a, a+ N) ;
}
template < class T1, class T2> void sortA_L( int N, T1 a[ ] , T2 b[ ] , void * mem = wmem) {
int i;
pair< T1, T2> * arr;
walloc1d( & arr, N, & mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
arr[ i] .first = a[ i] ;
arr[ i] .second = b[ i] ;
}
sort( arr, arr+ N) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
a[ i] = arr[ i] .first ;
b[ i] = arr[ i] .second ;
}
}
template < class S, class T> inline S chmax( S & a, T b) {
if ( a< b) {
a= b;
}
return a;
}
#define main dummy_main
int main( ) {
wmem = memarr;
return 0 ;
}
#undef main
int N;
int A[ 100000 ] ;
int M[ 100000 ] ;
class Solution{
public :
int minimumEffort( vector< vector< int >> & tasks) {
int i;
dummy_main( ) ;
int res = 0 ;
N = tasks.size ( ) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
A[ i] = tasks[ i] [ 0 ] ;
M[ i] = tasks[ i] [ 1 ] - A[ i] ;
}
sortA_L( N,M,A) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
chmax( res, max_L( res, M[ i] ) + A[ i] ) ;
}
return res;
}
}
;
// cLay version 20201121-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int N, A[1d5], M[1d5];
//
// class Solution {
// public:
// int minimumEffort(vector<vector<int>>& tasks) {
// dummy_main();
// int res = 0;
// N = tasks.size();
// rep(i,N) A[i] = tasks[i][0], M[i] = tasks[i][1] - A[i];
// sortA(N,M,A);
// rep(i,N) res >?= max(res, M[i]) + A[i];
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZvaWQqd21lbTsKY2hhciBtZW1hcnJbOTYwMDAwMDBdOwp0ZW1wbGF0ZTxjbGFzcyBTLCBjbGFzcyBUPiBpbmxpbmUgUyBtYXhfTChTIGEsVCBiKXsKICByZXR1cm4gYT49Yj9hOmI7Cn0KdGVtcGxhdGU8Y2xhc3MgVD4gaW5saW5lIHZvaWQgd2FsbG9jMWQoVCAqKmFyciwgaW50IHgsIHZvaWQgKiptZW0gPSAmd21lbSl7CiAgc3RhdGljIGludCBza2lwWzE2XSA9IHswLCAxNSwgMTQsIDEzLCAxMiwgMTEsIDEwLCA5LCA4LCA3LCA2LCA1LCA0LCAzLCAyLCAxfTsKICAoKm1lbSkgPSAodm9pZCopKCAoKGNoYXIqKSgqbWVtKSkgKyBza2lwWygodW5zaWduZWQgbG9uZyBsb25nKSgqbWVtKSkgJiAxNV0gKTsKICAoKmFycik9KFQqKSgqbWVtKTsKICAoKm1lbSk9KCgqYXJyKSt4KTsKfQp0ZW1wbGF0ZTxjbGFzcyBUPiBpbmxpbmUgdm9pZCB3YWxsb2MxZChUICoqYXJyLCBpbnQgeDEsIGludCB4Miwgdm9pZCAqKm1lbSA9ICZ3bWVtKXsKICB3YWxsb2MxZChhcnIsIHgyLXgxLCBtZW0pOwogICgqYXJyKSAtPSB4MTsKfQp0ZW1wbGF0ZTxjbGFzcyBUMT4gdm9pZCBzb3J0QV9MKGludCBOLCBUMSBhW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIHNvcnQoYSwgYStOKTsKfQp0ZW1wbGF0ZTxjbGFzcyBUMSwgY2xhc3MgVDI+IHZvaWQgc29ydEFfTChpbnQgTiwgVDEgYVtdLCBUMiBiW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIGludCBpOwogIHBhaXI8VDEsIFQyPiphcnI7CiAgd2FsbG9jMWQoJmFyciwgTiwgJm1lbSk7CiAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICBhcnJbaV0uZmlyc3QgPSBhW2ldOwogICAgYXJyW2ldLnNlY29uZCA9IGJbaV07CiAgfQogIHNvcnQoYXJyLCBhcnIrTik7CiAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICBhW2ldID0gYXJyW2ldLmZpcnN0OwogICAgYltpXSA9IGFycltpXS5zZWNvbmQ7CiAgfQp9CnRlbXBsYXRlPGNsYXNzIFMsIGNsYXNzIFQ+IGlubGluZSBTIGNobWF4KFMgJmEsIFQgYil7CiAgaWYoYTxiKXsKICAgIGE9YjsKICB9CiAgcmV0dXJuIGE7Cn0KI2RlZmluZSBtYWluIGR1bW15X21haW4KaW50IG1haW4oKXsKICB3bWVtID0gbWVtYXJyOwogIHJldHVybiAwOwp9CiN1bmRlZiBtYWluCmludCBOOwppbnQgQVsxMDAwMDBdOwppbnQgTVsxMDAwMDBdOwpjbGFzcyBTb2x1dGlvbnsKICBwdWJsaWM6CiAgaW50IG1pbmltdW1FZmZvcnQodmVjdG9yPHZlY3RvcjxpbnQ+PiYgdGFza3MpewogICAgaW50IGk7CiAgICBkdW1teV9tYWluKCk7CiAgICBpbnQgcmVzID0gMDsKICAgIE4gPSB0YXNrcy5zaXplKCk7CiAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgQVtpXSA9IHRhc2tzW2ldWzBdOwogICAgICBNW2ldID0gdGFza3NbaV1bMV0gLSBBW2ldOwogICAgfQogICAgc29ydEFfTChOLE0sQSk7CiAgICBmb3IoaT0oMCk7aTwoTik7aSsrKXsKICAgICAgY2htYXgocmVzLCBtYXhfTChyZXMsIE1baV0pKyBBW2ldKTsKICAgIH0KICAgIHJldHVybiByZXM7CiAgfQp9CjsKLy8gY0xheSB2ZXJzaW9uIDIwMjAxMTIxLTEKCi8vIC0tLSBvcmlnaW5hbCBjb2RlIC0tLQovLyAjZGVmaW5lIG1haW4gZHVtbXlfbWFpbgovLyB7fQovLyAjdW5kZWYgbWFpbgovLyAKLy8gaW50IE4sIEFbMWQ1XSwgTVsxZDVdOwovLyAKLy8gY2xhc3MgU29sdXRpb24gewovLyBwdWJsaWM6Ci8vICAgaW50IG1pbmltdW1FZmZvcnQodmVjdG9yPHZlY3RvcjxpbnQ+PiYgdGFza3MpIHsKLy8gICAgIGR1bW15X21haW4oKTsKLy8gICAgIGludCByZXMgPSAwOwovLyAgICAgTiA9IHRhc2tzLnNpemUoKTsKLy8gICAgIHJlcChpLE4pIEFbaV0gPSB0YXNrc1tpXVswXSwgTVtpXSA9IHRhc2tzW2ldWzFdIC0gQVtpXTsKLy8gICAgIHNvcnRBKE4sTSxBKTsKLy8gICAgIHJlcChpLE4pIHJlcyA+Pz0gbWF4KHJlcywgTVtpXSkgKyBBW2ldOwovLyAgICAgcmV0dXJuIHJlczsKLy8gICB9Ci8vIH07Cg==