/*
    给出m条船，n批人，每批a[i]+1个人，让该批人上将获益b[i]
    有个限制，这些船上的人必须按顺序
    如第一条船上1 3 第二条串上2 4 是不合法的
    因为2应排在3之前

    dp[M][K]表示第M条船用了容量K的最大价值，O(NMK)的算法行不通
    转化思维：
    dp[i]获得价值i需要最少的代价（占有的船的位置）
    http://blog.sina.com.cn/s/blog_677a3eb30100lkxk.html
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<cstdlib>
#include<iostream>

using namespace std;

const int INF = 1000000000;
const int MAXN = 10010;

int dp[MAXN];
int n , m , k;

int cal(int x,int y)//修改代价的累加
{
    int num =  (x+k-1)/k;
    if(x+y <= num*k)return x+y;
    return num*k+y;
}

int main() {

#ifdef ONLINE_JUDGE
#else
    freopen("in", "r", stdin);
#endif

    int T;
    int a,b;
    for(scanf("%d",&T) ; T--; )
    {
        scanf("%d%d%d",&n,&m,&k);
        dp[0] = 0;
        for(int i = 1 ; i <= 10000;  i++)
            dp[i] = INF;
        for(int i = 1 ; i <= n; i++)
        {
            scanf("%d%d",&a,&b);
            a++;//加上president本身
            for(int j = 10000 ;  j>=b ; j--)
            {
                if(dp[j-b] != INF)
                {
                    dp[j] = min( dp[j] , cal(dp[j-b] , a) );
                }
            }
        }
        int ans = 10000 ;
        while(dp[ans] > m*k ) ans --;
        printf("%d\n",ans);
    }
    return 0;
}