Convex Trick

void INSERT(Long m, Long c)
{
    Long m1, c1, m2, c2;
    while(head > tail+1)
    {
        m1 = DQ[head-1].first;
        c1 = DQ[head-1].second;
        m2 = DQ[head-2].first;
        c2 = DQ[head-2].second;

        if( (c2-c1)*(m2-m) >= (m2-m1)*(c2-c) )
            head--;
        /*if( (c2-c1)*(m1-m) >= (m2-m1)*(c1-c) )
            head--;*/
        else
            break;
    }

    DQ[head++] = PLL(m, c);
}

Long QUERY(Long x)
{
    Long m1, c1, m2, c2;
    while( head > tail+1 )
    {
        m1 = DQ[tail].first;
        c1 = DQ[tail].second;
        m2 = DQ[tail+1].first;
        c2 = DQ[tail+1].second;

        if(x*(m2-m1) >= (c2 - c1))
            tail++;
        else
            break;
    }

    return -DQ[tail].first*x + DQ[tail].second;
}
/* here storing positive m,actually -m , returns minimum */