Problem26984--学习ing

26984: 学习ing

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

楚神最近想要成为学霸,但是他现在的学习太渣了。
楚神这学期选修了N门课程,第i(1<=i<=N)门课程会有一个最高的等级l_i,但是楚神每门课程的初始等级都为1。楚神的目标是把第M门课修到最高等级,因为他天天在空间里晒妹结果一群人都把它拉黑了,没人想要带他飞,因此楚神只能花钱去报培训班。
现在有K个培训班,每个培训班都需要有一定的基础才能报,并且交钱学完后只能提升一门课程的等级。换句话说,报第j(1<=j<=K)个培训班的要求(先行课)是第x_j门课的等级修到y_j以上才行,花c_j块钱报名学完之后可以把他第s_j门课的等级提高到t_j级。

请问楚神至少要花多少钱才能达到目标。

Input

第一行输入一个整数T,表示有T组数据,对于每组数据第一行输入两个整数N,M(0<M<=N<=100),表示总共有N门课程,楚神的目标是把第M门课学到最高等级。
          接下来N行每行输入一个整数l_i(0<L_i<=10),表示第i门课程的最高等级。
          然后输入一个整数K(0<=K<=10^5)表示K个培训班。接下来输入K行,每行输入五个数x_i,y_i,s_i,t_i,c_i,(0<x_i,s_i<=N, 0<y_i,t_j<=l_(t_i), 0<c<1000),分别表示
          第i门课的先行课的课程序号和要求等级,学完之后的能提升的课程序号及该课程能到达的等级,以及这门课需要花费的金钱。

Output

每组数据输出一个整数,表示达到目标最少需要花的钱数,如果不能达到目标输出-1;

Sample Input Copy

2
2 2
2
2
2
2 1 1 2 3
1 2 2 2 3

2 2
2
2
3
1 1 2 2 3
2 1 1 2 3
1 2 2 2 3

Sample Output Copy

6
3

Source/Category