丽娃河的狼人传说

Time limit per test: 1.0 seconds

Time limit all tests: 1.0 seconds

Memory limit:  megabytes

丽娃河是华师大著名的风景线。但由于学校财政紧缺，丽娃河边的路灯年久失修，一到晚上就会出现走在河边要打着手电的情况，不仅非常不方便，而且影响安全：已经发生了大大小小的事故多起。

方便起见，丽娃河可以看成是从  到 n 的一条数轴。为了美观，路灯只能安装在整数点上，每个整数点只能安装一盏路灯。经专业勘测，有 m 个区间特别容易发生事故，所以至少要安装一定数量的路灯，

请问至少还要安装多少路灯。

Input

第一行一个整数 T (≤T≤)，表示测试数据组数。

对于每组数据：

    第一行三个整数 n,m,k (≤n≤,≤m≤,≤k≤n)。

    第二行 k 个不同的整数用空格隔开，表示这些位置一开始就有路灯。

    接下来 m 行表示约束条件。第 i 行三个整数 li,ri,ti 表示：第 i 个区间 [li,ri] 至少要安装 ti 盏路灯 (≤li≤ri≤n,≤ti≤n)。

Output

对于每组数据，输出 Case x: y。其中 x 表示测试数据编号（从  开始），y 表示至少要安装的路灯数目。如果无解，y 为 −。

Examples

Input

Output

Case :

Case :

Case : 

Note

因为今天不是满月，所以狼人没有出现。

Source

 华东师范大学网赛 

/**

题目：Problem #3263 丽娃河的狼人传说

链接：http://acm.ecnu.edu.cn/problem/3263/

题意：给定一个数n，表示一个1-n的数轴，给定一个k，表示数轴上k个位置已经安装了灯。给定一个m，表示有m个区间[l,r]，

每个区间后面有个整数值表示在这个区间至少要有多少盏灯。l,r都是整数。灯只可以安装在数轴的整数点上。

问至少要安装多少盏灯，才能使所有区间都满足自己要求的条件。如果无解，输出-1.

思路：贪心，对r进行排序即可。

*/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int,int> P;

const int maxn = 1e5+;

int T, n, m, k;

int lgt[];

struct node

{

    int l, r, t;

    bool operator < (const node&k)const {

        return r<k.r;

    }

}a[];

int main()

{

    cin>>T;

    int cas = ;

    while(T--)

    {

        scanf("%d%d%d",&n,&m,&k);

        memset(lgt, , sizeof lgt);

        for(int i = ; i <= k; i++){

            int x;

            scanf("%d",&x);

            lgt[x] = ;

        }

        int flag = ;

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

            scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].t);

            if(a[i].r-a[i].l+<a[i].t){flag = ;}

        }

        if(flag){

            printf("Case %d: -1\n",cas++) ; continue;

        }

        sort(a,a+m);

        int ans = ;

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

            int l = a[i].l, r = a[i].r;

            int cnt = ;

            for(int j = l; j <= r; j++){

                cnt += lgt[j];

            }

            if(cnt>=a[i].t) continue;

            cnt = a[i].t-cnt;

            for(int j = r; j >= l&&cnt; j--){

                if(lgt[j]==){

                    lgt[j] = ; cnt--;

                    ans ++;

                }

            }

        }

        printf("Case %d: %d\n",cas++,ans);

    }

    return ;

}