Description
神犇航空有K架飞机，为了简化问题，我们认为每架飞机都是相同的。神犇航空的世界中有N个机场，以0..N-1编号，其中0号为基地机场，每天0时刻起飞机才可以从该机场起飞，并不晚于T时刻回到该机场。一天，神犇航空接到了M个包机请求，每个请求为在s时刻从a机场起飞，在恰好t时刻到达b机场，可以净获利c。设计一种方案，使得总收益最大。
Input
第一行，4个正整数N,M,K,T，如题目描述中所述；
以下N行，每行N个整数，描述一个N*N的矩阵t，ti,j表示从机场i空载飞至机场j，需要时间ti,j；
以下N行, 每行N个整数，描述一个N*N的矩阵f，fi,j表示从机场i空载飞至机场j，需要费用fi,j；
以下M行，每行5个整数描述一个请求，依次为a,b,s,t,c。
以下N行，每行N个整数，描述一个N*N的矩阵t，ti,j表示从机场i空载飞至机场j，需要时间ti,j；
以下N行, 每行N个整数，描述一个N*N的矩阵f，fi,j表示从机场i空载飞至机场j，需要费用fi,j；
以下M行，每行5个整数描述一个请求，依次为a,b,s,t,c。
Output
仅一行，一个整数，表示最大收益。
Sample Input
2 1 1 100 5
5 0
0 5
5 0
0 1 0 5 10
Sample Output
5Hint
数据规模及约定
对于10%的测试数据，K=1；
另有20%的测试数据，K=2；
对于全部的测试数据，N,M<=200，K<=10，T<=3000，ti,j<=200，fi,j<=2000，0<=a,b<N，0<=s<=t<=T，0<=c<=10000，ti,i=fi,i=0，ti,j<=ti,k+tk,j，fi,j<=fi,k+fk,j。
