博客

The 2017 China Collegiate Programming Contest Qinhuangdao Site is coming! There will be


teams participating in the contest, and the contest will be held on a huge round table with


seats numbered from 1 to


in clockwise order around it. The


-th team will be seated on the


-th seat.

BaoBao, an enthusiast for competitive programming, has made


predictions of the contest result before the contest. Each prediction is in the form of


, which means the


-th team solves a problem during the


-th time unit.

As we know, when a team solves a problem, a balloon will be rewarded to that team. The participants will be unhappy if the balloons take almost centuries to come. If a team solves a problem during the


-th time unit, and the balloon is sent to them during the


-th time unit, then the unhappiness of the team will increase by


. In order to give out balloons timely, the organizers of the contest have bought a balloon robot.

At the beginning of the contest (that is to say, at the beginning of the 1st time unit), the robot will be put on the


-th seat and begin to move around the table. If the robot moves past a team which has won themselves some balloons after the robot’s last visit, it will give all the balloons they deserve to the team. During each unit of time, the following events will happen

in order

:

1. The robot moves to the next seat. That is to say, if the robot is currently on the
   
   
   -th (
   
   
   ) seat, it will move to the (
   
   
   )-th seat; If the robot is currently on the
   
   
   -th seat, it will move to the 1st seat.
2. The participants solve some problems according to BaoBao’s prediction.
3. The robot gives out balloons to the team seated on its current position if needed.

BaoBao is interested in minimizing the total unhappiness of all the teams. Your task is to select the starting position


of the robot and calculate the minimum total unhappiness of all the teams according to BaoBao’s predictions.

Input

There are multiple test cases. The first line of the input contains an integer


, indicating the number of test cases. For each test case:

The first line contains three integers


,


and


(


,


,


), indicating the number of participating teams, the number of seats and the number of predictions.

The second line contains


integers


(


, and


for all


), indicating the seat number of each team.

The following


lines each contains two integers


and


(


,


), indicating that the


-th team solves a problem at time


according to BaoBao’s predictions.

It is guaranteed that neither the sum of


nor the sum of


over all test cases will exceed


.

Output

For each test case output one integer, indicating the minimum total unhappiness of all the teams according to BaoBao’s predictions.

Sample Input

4
2 3 3
1 2
1 1
2 1
1 4
2 3 5
1 2
1 1
2 1
1 2
1 3
1 4
3 7 5
3 5 7
1 5
2 1
3 3
1 5
2 5
2 100 2
1 51
1 500
2 1000

Sample Output

1
4
5
50

Hint

For the first sample test case, if we choose the starting position to be the 1st seat, the total unhappiness will be (3-1) + (1-1) + (6-4) = 4. If we choose the 2nd seat, the total unhappiness will be (2-1) + (3-1) + (5-4) = 4. If we choose the 3rd seat, the total unhappiness will be (1-1) + (2-1) + (4-4) = 1. So the answer is 1.

For the second sample test case, if we choose the starting position to be the 1st seat, the total unhappiness will be (3-1) + (1-1) + (3-2) + (3-3) + (6-4) = 5. If we choose the 2nd seat, the total unhappiness will be (2-1) + (3-1) + (2-2) + (5-3) + (5-4) = 6. If we choose the 3rd seat, the total unhappiness will be (1-1) + (2-1) + (4-2) + (4-3) + (4-4) = 4. So the answer is 4.

题目大意：

一个机器人起始点为k（我们去设定），每秒机器人先向前走一步，然后看看能否发当前位子的队伍气球，如果可以，将会发给他们气球，当一个队伍在时间x过了一个题之后， 如果我们在时刻y去送到气球，那么这个队伍会产生不开心值为y-x；问我们总共的不开心值最小是多少。

思路：

①首先我们可以计算出机器人一开始在点1的情况下每个任务的不开心值，我们设定为d【i】；

②很显然，我们移动机器人的起始位子的目的是想让某些任务的不开心值下降，那么我们对于任务i，我们希望其不开心值下降d【i】个单位的话，就需要将机器人向右挪动d【i】个单位，同时我们去维护其他任务的不开心值计算即可。

Ac代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define ll long long int
ll d[1500000];
ll s[1500000];
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll sum=0;
        ll n,m,q;scanf("%lld%lld%lld",&n,&m,&q);
        for(ll i=1;i<=n;i++)scanf("%lld",&s[i]);
        for(ll i=0;i<q;i++)
        {
            ll x,y;scanf("%lld%lld",&x,&y);
            d[i]=(s[x]-1-y%m+m)%m;
            sum=sum+d[i];
        }
        ll ans=100000000000000000;
        sort(d,d+q);
        for(int i=0;i<q;i++)
        {
            ans=min(ans,sum+i*m-d[i]*q);
        }
        printf("%lld\n",ans);
    }
}

4
2 3 3
1 2
1 1
2 1
1 4
2 3 5
1 2
1 1
2 1
1 2
1 3
1 4
3 7 5
3 5 7
1 5
2 1
3 3
1 5
2 5
2 100 2
1 51
1 500
2 1000

1
4
5
50