题目背景

1. wqs爱好模拟飞行。

2. clj开了一家神犇航空，由于clj还要玩游戏，所以公司的事务由你来打理。

注意：题目中只是用了这样一个背景，并不与真实/模拟飞行相符

题目描述

神犇航空有$K$架飞机，为了简化问题，我们认为每架飞机都是相同的。神犇航空的世界中有$N$个机场，以$0\cdots N-1$编号，其中$0$号为基地机场，每天0时刻起飞机才可以从该机场起飞，并不晚于$T$时刻回到该机场。一天，神犇航空接到了$M$个包机请求，每个请求为在$s$时刻从$a$机场起飞，在恰好$t$时刻到达$b$机场，可以净获利$c$。设计一种方案，使得总收益最大。

输入格式

第一行，4个正整数$N,M,K,T$，如题目描述中所述；

以下$N$行，每行$N$个整数，描述一个$N*N$的矩阵$t$， $t­_{ij}$ 表示从机场$i$空载飞至机场$j$，需要时间 $t_{ij}$ ；

以下$N$行, 每行$N$个整数，描述一个$N*N$的矩阵$f$， $f_{­ij}$ 表示从机场$i$空载飞至机场$j$，需要费用 $f_{ij}$ ；

以下$M$行，每行$5$个整数描述一个请求，依次为$a,b,s,t,c$。

输出格式

仅一行，一个整数，表示最大收益。

2 1 1 10
0 5
5 0
0 5
5 0
0 1 0 5 10

5

提示

对于10%的测试数据，$K=1$；

另有20%的测试数据，$K=2$；

对于全部的测试数据，$N,M<=200$，$K<=10$，$T<=3000$，$t_{ij}<=200$，$f_{ij}<=2000$，$0<=a,b<N$，$0<=s<=t<=T$，$0<=c<=10000$，$t_{ii}=f_{ii}=0$，$t_{ij}<=t_{ik}+t_{kj}$，$f_{ij}<=f_{ik}+f_{kj}$。