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

 

题意：给一个圈，设起点为0，给出周长为L，在圈中有 n 棵树，依次给出按顺时针方向与起点的距离，树上的苹果数。给出篮子大小（最多能装的苹果树）。问最少走多远可以采集完所有苹果。

 

思路：

以过起点的直径为界，以苹果树在左半圆和右半圆分别贪心，得到要走的距离。最后枚举最后走一整圈所采集的苹果（详见代码）。比较得出最小值。

#include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define maxn 100050  int d_l[maxn],d_r[maxn],l,n,k,t,x,a,L,R;long long tot_l[maxn],tot_r[maxn],ans,tmp;int main(){    scanf("%d",&t);    while(t--){        L=R=0;        scanf("%d%d%d",&l,&n,&k);        for(int i=0;i