Description

Shenniu Airlines has $K$ airplanes. To simplify the problem, assume all airplanes are identical. In the world of Shenniu Airlines, there are $N$ airports, numbered $0 \cdots N-1$, where airport $0$ is the base. All $K$ airplanes are at airport $0$ at time $0$, may take off starting from time $0$, and must return to airport $0$ no later than time $T$.

During one day, the company receives $M$ charter requests. Each request is: depart from airport $a$ at time $s$, arrive at airport $b$ exactly at time $t$, and earn a net profit of $c$. In other words, if you assign an airplane at time $s$ at airport $a$ to this request, that airplane will appear at airport $b$ at time $t$, and you will gain a net profit of $c$.

Design a plan to maximize the total profit.

Input Format

• The first line contains $4$ positive integers $N, M, K, T$, as described above.
• The next $N$ lines each contain $N$ integers, describing an $N \times N$ matrix $t$, where $t_{i,j}$ is the time needed to ferry (empty flight) from airport $i$ to airport $j$.
• The next $N$ lines each contain $N$ integers, describing an $N \times N$ matrix $f$, where $f_{i,j}$ is the cost to ferry from airport $i$ to airport $j$.
• The next $M$ lines each describe one request with $5$ integers: $a, b, s, t, c$.

Output Format

Output a single line with one integer: the maximum profit.

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

5

Hint

• For $10\%$ of the testdata, $K = 1$.
• For another $20\%$ of the testdata, $K = 2$.
• For all the testdata: $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_{i,j} \le t_{i,k} + t_{k,j}$, $f_{i,j} \le f_{i,k} + f_{k,j}$.

Translated by ChatGPT 5