Alice likes to collect stamps. She is now at the post office buying some new stamps.
There are NN different kinds of stamps that exist in the world; they are numbered 11 through NN . However, stamps are not sold individually; they must be purchased in sets. There are MM different stamp sets available; the ithith set contains the stamps numbered LiLi through RiRi . The same stamp might appear in more than one set, and it is possible that one or more stamps are not available in any of the sets.
All of the sets cost the same amount; because Alice has a limited budget, she can buy at most KK different sets. What is the maximum number of different kinds of stamps that Alice can get?

Input

The input starts with one line containing one integer TT , the number of test cases.TT test cases follow.
Each test case begins with a line containing three integers: NN , MM , and KK : the number of different kinds of stamps available, the number of stamp sets available, and the maximum number of stamp sets that Alice can buy.
MM lines follow; the ithoftheselinesrepresentstheithoftheselinesrepresentsthe i^{th} stamp set and contains two integers, LiLi and RiRi , which represent the inclusive range of the numbers of the stamps available in that set.
1≤T≤1001≤T≤100
1≤K≤M1≤K≤M
1≤N,M≤20001≤N,M≤2000
1≤Li≤Ri≤N1≤Li≤Ri≤N

Output

For each test case, output one line containing “Case #x: y”, where xx is the test case number (starting from 1) and yy is the maximum number of different kinds of stamp that Alice could get.

Sample Input

2
5 3 2
3 4
1 1
1 3
100 2 1
1 50
90 100

Sample Output

Case #1: 4
Case #2: 50

Hint

In sample case #1, Alice could buy the first and the third stamp sets, which contain the first four kinds
of stamp. Note that she gets two copies of stamp 3, but only the number of different kinds of stamps
matters, not the number of stamps of each kind.
In sample case #2, Alice could buy the first stamp set, which contains 50 different kinds of stamps.

对于一个区间（l,r），不用存l,r；up[]记录每一点最远能延伸到的位置。

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+30;
int dp[N][N],up[N];
int main()
{
    int t,n,m,k,kcase=0;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        memset(up,0,sizeof(up));
        scanf("%d%d%d",&n,&m,&k);
        int l,r;
        while(m--)
        {
            scanf("%d%d",&l,&r);
            for(int i=l;i<=r;i++)
                up[i]=max(up[i],r);///存下每一张邮票最远能延伸到的位置
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<k;j++)
            {
                dp[i][j+1]=max(dp[i][j+1],dp[i-1][j+1]);///对于当前的一套邮票，两种可能，选或者不选
                if(up[i])///如果存在一套邮票可以从这张邮票延伸到后面（最大值）
                    dp[up[i]][j+1]=max(dp[up[i]][j+1],dp[i-1][j]+up[i]-i+1);///更新后面的值
            }
        }
        cout<<"Case #"<<++kcase<<": "<<dp[n][k]<<'\n';
    }
    return 0;
}