long comp(vector<long> &a, vector<long> &b)
{
    return a[0] < b[0];
}
long minimumAverage(vector<vector<long>> customers)
{
    sort(customers.begin(), customers.end(), comp);
    multiset<long> waits;
    long visited = 0;
    auto leftIte = customers.begin();
    long res = 0;
    long timeline = customers[0][0];
    auto rightIte = customers.begin();
    while (visited < customers.size())
    {
        rightIte = upper_bound(leftIte, customers.end(),
                               timeline, [](long val, vector<long> &a)
                               { return a[0] > val; });
        auto it = leftIte;
        while (it != rightIte) {
            waits.insert((*it)[1]);
            it += 1;
        }

        if (waits.size() == 0)
        {
            timeline += (*leftIte)[0];
            continue;
        }
        long minVal = *waits.begin();
        res += waits.size() * minVal;
        waits.erase(waits.begin(), next(waits.begin()));
        it = leftIte;
        while (it < customers.end())
        {
            if (timeline >= (*it)[0])
            {
                it += 1;
            }
            else if ((*it)[0] <= timeline + minVal)
            {
                res += timeline + minVal - (*it)[0];
                waits.insert((*it)[1]);
                it += 1;
            }
            else
            {
                break;
            }
        }
        timeline += minVal;
        visited += 1;
        leftIte = it;
    }

    return res / customers.size();
}