Convex Trick

#define pb push_back
typedef long long Long;
vector<Long> VC,VM;
Long Pt;
bool IsBad( Long i,Long j,Long k ){
    return (double)( VC[i]-VC[j] )/( VM[j]-VM[i] )  >= (double)( VC[i]-VC[k] )/( VM[k]-VM[i] );
}
void Add( Long c,Long m ){
    VC.pb( c );
    VM.pb( m );
    while( VC.size()>=3 && IsBad( VC.size()-3,VC.size()-2,VC.size()-1 ) ){
        VC.erase( VC.end()-2 );
        VM.erase( VM.end()-2 );
    }
}
Long Query( Long x ){
    Pt = min( Pt,(Long)VC.size()-1 );
    while( Pt<VC.size()-1 && VC[Pt]+VM[Pt]*x >= VC[Pt+1]+VM[Pt+1]*x ) Pt++;
    return VC[Pt] + VM[Pt]*x;
}