Linyong GAN

the idea is very straight forward. Choose the largest and the smallest to match a pair, so that it would be the optimal solution. leverage 2 pts to achieve that.

The most difficult part of this question is the domain of N and M.

Approach 1

store y in an array one by one.

for(int i = 0; i < n; i++)
{
    int x, long long y;
    scanf("%d%lld", &x, &y);
    for(int j = 0; j < x; j++) cow[m++] = y;
}

however, M could up to 1e9, it's not acceptable for C++.

Approach 2

store x and y in an array, and reduce that one by one.

while(l < r || (l == r && cow[l].x != 0))
{
    mx = max(mx, cow[l].y+cow[r].y);
    cow[l].x--, cow[r].x--;
    if(cow[l].x==0) l++;
    if(cow[r].x==0) r--;
}

however, reduce one by one is too slow. only 10 pts, but very approach to the solution.

Approach 3

rather than reduce one by one, reduce the largest number.

while(...)
{
    mx = ...
    if(cow[l].x > cow[r].x)
    {
        cow[l].x -= cow[r].x;
        r--;
    }
    else if(cow[r].x > cow[l].x)
    {
        ...
    }
    else
    {
        l++, r--;
    }
}