主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 F: 国队陪迷妹

问题 F: 国队陪迷妹

时间限制: 10 Sec  内存限制: 128 MB
提交: 59  解决: 11
[提交][状态][讨论版]

题目描述

作为XDU最有魅力的ACMerGMH自然有许多小迷妹。日理万机的GMH为了哄迷妹们开心,决心在接下来的n天里抽出一些时间来陪m个妹子(至于怎么陪请自行脑补)。对每个迷妹,GMH当天至少要抽出l[i]的时间才能令她满意。然而他太优秀了,为了不让其他迷妹吃醋,每个妹子每天陪伴不能超过r[i]的时间。他决定每天抽出不多于dmax[j]的时间来泡妞,然而这还是引起了cyt的不满。Cyt决定加大对他的训练强度,苦逼的GMH现在每天akcyt出的题目后发现每个妹子n天里最多还能陪伴gmax的时间。每个妹子n天里要一共得到最少gmin时间的陪伴,否则她们就会闹分手。现在GMH想知道n天里能有多少时间来陪自己的迷妹,然而它的时间很宝贵,不想在这种简单问题上浪费时间。作为他的迷妹(弟),你能帮帮他吗?

输入

多组测试数据;

每组数据第一行两个正整数n,m (n<=365  m<=1000)

接下来m行,每行两个正整数gmingmax,表示每个妹子一共需要陪伴的时间在[gmin,gmax]之间。0<gmin,gmax<=10^9;

接下来n天,每一部分两个正整数cdmax0<c<=m;0<=dmax<=10^9),dmax表示每天至多抽出dmax的时间;

接下来c行,每行三个正整数t,l[t],r[t],表示第i天第t个妹子需要[l[t],r[t]]的时间。(0<=t<m,0<=l[t],r[t]<=30000

输出

对每组数据输出一行,表示n天陪伴妹子的最大时间,若不存在一组解符合,则输出” orz_GMH”(不包含引号)。

样例输入

2 3
12 15
12 15 
12 15
3 18
0 3 9
1 3 9
2 3 9
3 18
0 3 9
1 3 9
2 3 9

2 3
12 12
12 12
12 12
3 18
0 3 9
1 3 9
2 3 9
3 18
0 0 3
1 3 6
2 6 9

2 3
12 300
12 300
12 300
3 15
0 3 9
1 3 9
2 3 9
3 21
0 0 3
1 3 6
2 6 12

样例输出

36
36
orz_GMH

提示

[提交][状态][讨论版]