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

2

10 3 2

2 2

8 2

5 1

10 4 1

2 2

8 2

5 1

0 10000

Sample Output

18

26

Source

2015 Multi-University Training Conest 2

这题若是道路不是圈的话，就左右两边贪心可得最短路程，但由于道路是圆圈，所以可以走整圈。具体的分析在代码。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define LL long longconst int N=100000+50;using namespace std;int X[N],a[N],b[N];LL sum1[N],sum2[N];int main(){ int t,l,num,k; cin>>t; while(t--) { memset(a,0,sizeof(a)) ; memset(b,0,sizeof(b)) ; memset(sum1,0,sizeof(sum1)) ; memset(sum2,0,sizeof(sum2)) ; cin>>l>>num>>k; int x,y; int n=0; while(num--) { cin>>x>>y; for(int i=1;i<=y;i++) X[++n]=x;//先求出每个苹果的位置。 } int n1=0,n2=0; for(int i=1;i<=n;i++) { if(2*X[i]<=l) a[++n1]=X[i];//原点右边的每个苹果所在的位置 else b[++n2]=l-X[i];//原点左边的每个苹果所在的位置 } sort(a+1,a+1+n1); sort(b+1,b+1+n2); sum1[0]=sum2[0]=0; for(int i=1;i<=n1;i++) { if(i<=k) sum1[i]=a[i]; else sum1[i]=sum1[i-k]+a[i]; } //算出摘完右边的苹果所用的的路程 for(int i=1;i<=n2;i++) { if(i<=k) sum2[i]=b[i]; else sum2[i]=sum2[i-k]+b[i]; }//算出摘完左边的苹果所用的的路程 LL ans=(sum1[n1]+sum2[n2])*2; for(int i=0;i<=n1&&i<=k;i++)//枚举若是摘右边的苹果时走整圈时的距离，然后和不走整圈时哪个答案小 { int left=n1-i;//右边所剩的苹果数 int right=max(0,n2-(k-i));//装完篮子后左边所剩的苹果数 ans=min(ans,l+(sum1[left]+sum2[right])*2); } printf("%lld\n",ans); } return 0;}