Problem Description

There are n apple
trees planted along a cyclic road, which is L metres
long. Your storehouse is built at position 0 on
that cyclic road.
The ith
tree is planted at position xi,
clockwise from position 0.
There are ai delicious
apple(s) on the ith
tree.

You only have a basket which can contain at most K apple(s).
You are to start from your storehouse, pick all the apples and carry them back to your storehouse using your basket. What is your minimum distance travelled?

1≤n,k≤105,ai≥1,a1+a2+...+an≤105
1≤L≤109
0≤x[i]≤L

There are less than 20 huge testcases, and less than 500 small testcases.

 

Input

First line: t,
the number of testcases.
Then t testcases
follow. In each testcase:
First line contains three integers, L,n,K.
Next n lines,
each line contains xi,ai.

 

Output

Output total distance in a line for each testcase.

 

Sample Input

 

Sample Output

 

Author

XJZX

 

Source

2015 Multi-University Training Contest 2

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define MAX 100050

long long sum_left[MAX];

long long sum_right[MAX];

int l[MAX],r[MAX];

long long ans;

int Left,Right;

int n,k,len,T,a,b;

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        memset(sum_left,0,sizeof(sum_left));

        memset(sum_right,0,sizeof(sum_right));

        scanf("%d%d%d",&len,&n,&k);

        Left=0,Right=0;

        for(int i=0; i<n; i++)

        {

            scanf("%d%d",&a,&b);

            for(int j=0; j<b; j++)

            {

                if(a*2<len)

                   l[++Left]=a;

                else

                    r[++Right]=len-a;

            }

        }

        sort(l+1,l+Left+1);

        sort(r+1,r+Right+1);

        for(int i=1; i<=Left; i++)

        {

            if(i<=k)

                sum_left[i]=l[i];

            else

                sum_left[i]=sum_left[i-k]+l[i];

        }

        for(int i=1; i<=Right; i++)

        {

            if(i<=k)

                sum_right[i]=r[i];

            else

                sum_right[i]=sum_right[i-k]+r[i];

        }

        ans=(sum_left[Left]+sum_right[Right])*2;

        for(int i=0; i<=k && i <= Left; i++)

        {

            long long lll = (sum_left[Left-i]+sum_right[max(0,Right-(k-i))])*2;

            ans=min(ans,len+lll);

        }

        printf("%I64d\n",ans);

    }

    return 0;

}