[国家集训队]航班安排

题目背景

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$。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

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}$。