Description

神犇航空有 $K$ 架飞机，为了简化问题，我们认为每架飞机都是相同的。神犇航空的世界中有 $N$ 个机场，以 $0\cdots N-1$ 编号，其中 $0$ 号为基地机场，每天 $0$ 时刻起飞机才可以从该机场起飞，并不晚于 $T$ 时刻回到该机场。

一天，神犇航空接到了 $M$ 个包机请求，每个请求为在 $s$ 时刻从 $a$ 机场起飞，在恰好 $t$ 时刻到达 $b$ 机场，可以净获利 $c$。换言之，你只需要在 $s$ 时刻在 $a$ 机场选择提供一架飞机给请求方，那么这架飞机就会在 $t$ 时刻准时出现在 $b$ 机场，并且你将获得 $c$ 的净利润。

设计一种方案，使得总收益最大。

Input Format

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

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

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

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

Output Format

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

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

5

Hint

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

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

对于全部的测试数据，$1\le N,M\le 200$，$1\le K\le 10$，$1\le T\le 3000$，$1\le t_{i,j}\le 200$，$f_{i,j}\le 2\times 10^3$，$0\le a,b<N$，$0\le s\le t\le T$，$0\le c\le 10000$，$t_{i,i}=f_{i,i}=0$，$t_{ij}\le t_{i,k}+t_{k,j}$，$f_{i,j}\le f_{i,k}+f_{k,j}$。