// 仅以此题，表示自己的成长之路
// 多校的一道题目，
// 题意在一个圆上有n棵苹果树，每个苹果树上有a[i]个苹果
// 从起点0出发，告诉你圆的周长L，你有一个篮子，容量为k
//求从起点0出发将所有苹果树 上的苹果都搬到0处所花费的最小的距离。// 解题思路
// 最开始我想到的是训练指南上的捡垃圾的dp那道题目，
// 不过一个是一维轴，一个是二维坐标，就类比了一下
// 怪自己技术太搓了，折腾了三个多小时，最后才在学长的
// 帮助之下过了这道题目// 我用的是dp的思路
// 先将所有的苹果树拆开成只有一个苹果的cnt棵树
// dp[i]表示捡完前i棵苹果所走的最小的距离
// 很容易想到dp[i] = min(dp[j] + cost) 1<= j <= i;
// 这个cost就是j后面的第j+1的点到0的距离和它到第i个点的距离
// 再加上第i个点回到0的距离
// 因为是一个圆，可以顺时针，也可以逆时针走
// 再处理一个前缀和
// dp[i] = min(dp[j] - total_dist[j+1] + min(dist[j+1],((L-dist[j+1])+L)%L))
// + total_dist[i] + min(dist[i],(L-dist[i] + L)%L);
// 即维护一个func(j)最小值，我用的是单调队列优化。
// 堆优化的话应该也可以做，不过应该会慢一些。// 说实在的，其实沉下心来钻研一道题目还是很有收获的，
// 心是静的，继续加油吧，题解说可以贪心做，小子实在是
// 无法想到，也不会，如果有大牛有任何想法，希望可以不吝惜
// 地教教小子，小子一定不胜感激#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 1000;
ll d[maxn*2];
int n,L,k;
int cnt;
struct node {int pos;int val;
};
node a[maxn*2];
bool cmp(node a,node b){return a.pos<b.pos;
}ll total_dist[maxn*2],total_weight[maxn*2];
ll dist[maxn*2];
ll deq[maxn*2];void print(){for (int i=1;i<cnt;i++){printf("%d %d %d %d\n",total_dist[i],total_weight[i],dist[i],d[i]);}
}void out(){for (int i=1;i<cnt;i++){printf("%d %d %d\n",i,a[i].pos,a[i].val);}
}void input(){memset(d,0,sizeof(d));memset(deq,0,sizeof(deq));memset(total_dist,0,sizeof(total_dist));memset(total_weight,0,sizeof(total_weight));memset(dist,0,sizeof(dist));memset(a,0,sizeof(a));scanf("%d%d%d",&L,&n,&k);cnt = 1;int u,v;for (int i=0;i<n;i++){scanf("%d%d",&u,&v);if (u==0 || u == L)continue;while(v>0){a[cnt].pos = u;a[cnt++].val = 1;v--;}}//out();// if (cnt==1){
// printf("0\n");
// return ;
// }sort(a+1,a+cnt,cmp);total_weight[0] = 0;total_dist[0] = 0;for (int i=1;i<cnt;i++){total_weight[i] = total_weight[i-1] + a[i].val;total_dist[i] = total_dist[i-1] + a[i].pos - a[i-1].pos;dist[i] = a[i].pos;}}ll func(int i){return d[i] - total_dist[i+1] + min(dist[i+1],((L-dist[i+1])+L)%L);
}void solve(){int head,tail;head = tail = 1;for (int i=1;i<cnt;i++){while(tail>=head && total_weight[i] - total_weight[deq[head]] > k)head++;d[i] = func(deq[head]) + total_dist[i] + min(dist[i],(L-dist[i] + L)%L);//printf("i = %d %d %d func[deq[%d]] = %d deq[head]=%d\n",i,deq[head],d[i],head,func(deq[head]),deq[head]);while(head<=tail && func(i) <= func(deq[tail]))tail--;deq[++tail] = i;}printf("%I64d\n",d[cnt-1]);//print();}int main(){int t;//freopen("1.txt","r",stdin);scanf("%d",&t);while(t--){input();solve();}return 0;
}
