# CFR 795 B. Significant Cups ( Monotonicity )

Problem - B - Codeforces

The first line contains three integers n, m and d (1 ≤ n, m ≤ 100 000, 1 ≤ d ≤ 1e9) — the number of cups for Physics olympiads, the number of cups for Informatics olympiads and the width of the shelf.
Each of the following n lines contains two integers ci and wi (1 ≤ ci, wi ≤ 1e9) — significance and width of the i-th cup for Physics olympiads.
Each of the following m lines contains two integers cj and wj (1 ≤ cj, wj ≤ 1e9) — significance and width of the j-th cup for Informatics olympiads.

O( N + M )

```var _ = readline().split( ' ' );
var N = +_[ 0 ]; // + to cast string to int
var M = +_[ 1  ];
var D = +_[ 2 ];
function cmp( a, b ) {
var x, y;
if( a[ 0 ] != b[ 0 ] ) {
x = -a[ 0 ];
y = -b[ 0 ];
} else {
x = a[ 1 ];
y = b[ 1 ];
}
if( x < y ) return -1;
else if( x === y ) return 0;
return 1;
}
var ACW = [];
for( var i = 0; i < N; ++i ) {
var __ = readline().split( ' ' );
ACW.push( [ +__[ 0 ], +__[ 1 ] ] );
}
ACW.sort( cmp );
var BCW = [];
for( var i = 0; i < M; ++i ) {
var __ = readline().split( ' ' );
BCW.push( [ +__[ 0 ], +__[ 1 ] ] );
}
BCW.sort( cmp );
var curc = 0;
var curw = 0;
var bptr = 0; // [ 0, bptr )
while( bptr < M ) {
if( curw + BCW[ bptr ][ 1 ] > D ) break;
curw += BCW[ bptr ][ 1 ];
curc += BCW[ bptr ][ 0 ];
++bptr;
}
var ans = 0;
for( var aptr = 0; aptr < N; ++aptr ) {
curw += ACW[ aptr ][ 1 ];
curc += ACW[ aptr ][ 0 ];
while( curw > D && bptr > 0 ) {
--bptr;
curw -= BCW[ bptr ][ 1 ];
curc -= BCW[ bptr ][ 0 ];
}
if( bptr === 0 || curw > D ) break;
ans = Math.max( ans, curc );
}
print( ans );
```