Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem F: 二队-宁波-暗杀教室

Problem F: 二队-宁波-暗杀教室

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

我等,乃杀手,目标是、老师。
开学第一天,三年E班的同学,为了暗杀老师,决定发动了弹幕射击。
已知上课时,杀老师只会在讲台范围内移动。讲台可划分为N个空间块,从左到右编号分别为0~N-1。由于杀老师的速度高达20马赫,弹幕攻击需要对每个空间块至少造成一定封锁力度,才能有希望暗杀成功。对第i个空间块,至少需要造成p[i]个单位的封锁力度。
同学们有M种武器可供选择。每一把第i种武器,能对L[i]~R[i]的空间块发动弹幕射击,产生1个单位的封锁力度。由于预算充足,武器数量没有限制,可以使用多个同种武器。但是班级人力资源有限,每使用一把第i种武器,需要消耗班级人力资源c[i]。
班长forever97希望消耗尽量少的班级人力资源,以便大家放学后能去女仆咖啡厅。你能帮他吗?

Input

第一行只包含一个整数T(1≤T≤20),表示有T组数据。
对于每组数据,其第一行包含两个整数N(1≤N≤100)和M(1≤M≤1000),分别代表空间块数量和武器种数。
接下来一行,包含N个整数p[i](0≤p[i]≤100),表示对第i个空间至少需要造成的封锁力度。
接下来M行,每行包含三个整数L[i],R[i],c[i](1≤L[i]≤R[i]≤N,1≤c[i]≤100),表示第i种武器的攻击范围和每把武器所需的人力资源花费。 武器种类繁多,保证能对所有空间块发动弹幕射击。

Output

对于每组数据,输出一行结果。
输出格式为“Case #x: y”,x表示数据组数(从1开始),y表示答案。

Sample Input

2
2 2
2 3
1 1 2
2 2 3
3 3
2 3 4
1 2 2
2 3 5
3 3 2

Sample Output

Case #1: 13
Case #2: 14

HINT

[Submit][Status][Web Board]