<s> from sys import stdin <EOL> __all__ = [ "<STR_LIT>" , "<STR_LIT>" , <EOL> "<STR_LIT>" , "<STR_LIT>" ] <EOL> def _readint ( ) : <EOL> return int ( stdin . readline ( ) ) <EOL> def _readarray ( f ) : <EOL> return tuple ( map ( f , stdin . readline ( ) . split ( ) ) ) <EOL> def discrete_binary_search ( tab , lo , hi ) : <EOL> """<STR_LIT>""" <EOL> while lo < hi : <EOL> mid = lo + ( hi - lo ) // <NUM_LIT:2> <EOL> if tab [ mid ] : <EOL> hi = mid <EOL> else : <EOL> lo = mid + <NUM_LIT:1> <EOL> return lo <EOL> def continuous_binary_search ( f , lo , hi , gap = <NUM_LIT> ) : <EOL> """<STR_LIT>""" <EOL> while hi - lo > gap : <EOL> mid = ( lo + hi ) / <NUM_LIT:2> <EOL> if f ( mid ) : <EOL> hi = mid <EOL> else : <EOL> lo = mid <EOL> return lo <EOL> def optimized_binary_search_lower ( tab , logsize ) : <EOL> """<STR_LIT>""" <EOL> lo = <NUM_LIT:0> <EOL> intervalsize = ( <NUM_LIT:1> << logsize ) >> <NUM_LIT:1> <EOL> while intervalsize > <NUM_LIT:0> : <EOL> if not tab [ lo | intervalsize ] : <EOL> lo |= intervalsize <EOL> intervalsize >>= <NUM_LIT:1> <EOL> return lo <EOL> def optimized_binary_search ( tab , logsize ) : <EOL> """<STR_LIT>""" <EOL> hi = ( <NUM_LIT:1> << logsize ) - <NUM_LIT:1> <EOL> intervalsize = ( <NUM_LIT:1> << logsize ) >> <NUM_LIT:1> <EOL> while intervalsize > <NUM_LIT:0> : <EOL> if tab [ hi ^ intervalsize ] : <EOL> hi ^= intervalsize <EOL> intervalsize >>= <NUM_LIT:1> <EOL> return hi <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> def volume ( level ) : <EOL> vol = <NUM_LIT:0> <EOL> for base , height , ground in rect : <EOL> if base < level : <EOL> vol += ground * min ( level - base , height ) <EOL> return vol <EOL> for test in range ( _readint ( ) ) : <EOL> n = _readint ( ) <EOL> rect = [ ] <EOL> for _ in range ( n ) : <EOL> x , y , w , h = _readarray ( int ) <EOL> rect . append ( ( x , y , w * h ) ) <EOL> V = _readint ( ) <EOL> hi = <NUM_LIT> + <NUM_LIT> <EOL> if volume ( hi ) < V : <EOL> print ( "<STR_LIT>" ) <EOL> else : <EOL> print ( "<STR_LIT>" % <EOL> continuous_binary_search ( lambda x : volume ( x ) >= V , <NUM_LIT:0> , hi ) ) </s>
