Problem Description

There are  apple
trees planted along a cyclic road, which is  metres
long. Your storehouse is built at position  on
that cyclic road.

The 

rev=2.4-beta-2" alt="" style="">th
tree is planted at position 

rev=2.4-beta-2" alt="" style="">,
clockwise from position .
There are 

rev=2.4-beta-2" alt="" style=""> delicious
apple(s) on the 

rev=2.4-beta-2" alt="" style="">th
tree.



You only have a basket which can contain at most 

rev=2.4-beta-2" alt="" style=""> 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?

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">



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

 

Input

First line: ,
the number of testcases.

Then  testcases
follow. In each testcase:

First line contains three integers, 

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">.

Next 

rev=2.4-beta-2" alt="" style=""> lines,
each line contains 

rev=2.4-beta-2" alt="" style="">

rev=2.4-beta-2" alt="" style="">.

 

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

 

解题思路:

注意到，最多仅仅有一次会绕整个圈走一次。因此，先贪心的处理左半环和右半环。然后枚举绕整圈的时候从左側摘得苹果和从右側摘得苹果的数目。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <vector>

#include <queue>

#include <stack>

#include <cmath>

#include <algorithm>

#define LL long long

using namespace std;

const int MAXN = 100000 + 10;

int L, N, K;

LL x[MAXN];

LL ld[MAXN], rd[MAXN];

vector<LL>l, r;

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d%d", &L, &N, &K);

        l.clear(); r.clear();

        int pos, num, m = 0;

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

        {

            scanf("%d%d", &pos, &num);

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

                x[++m] = (LL)pos;

        }

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

        {

            if(2 * x[i] < L) l.push_back(x[i]);

            else r.push_back(L - x[i]);

        }

        sort(l.begin(), l.end()); sort(r.begin(), r.end());

        int lsz = l.size(), rsz = r.size();

        memset(ld, 0, sizeof(ld)); memset(rd, 0, sizeof(rd));

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

            ld[i + 1] = (i + 1 <= K ? l[i] : ld[i + 1 - K] + l[i]);

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

            rd[i + 1] = (i + 1 <= K ? r[i] : rd[i + 1 - K] + r[i]);

        LL ans = (ld[lsz] + rd[rsz]) * 2;

        for(int i=0;i<=lsz&&i<=K;i++)

        {

            int p1 = lsz - i;

            int p2 = max(0, rsz-(K-i));

            ans = min(ans, 2*(ld[p1] + rd[p2]) + L);

        }

        cout << ans << endl;

    }

    return 0;

}