Background

Luogu’s testdata is only for non-official sharing and communication, and is not the official testdata. Official judging link: https://www.cspro.org/.

Problem Description

The road map of Xixi Aifu Island can be viewed as a graph with $N$ nodes and $M$ directed edges. Node $i$ ($0 \le i < N$) has a color label $C[i] \in \{0, 1, \cdots, K - 1\}$. Edge $j$ ($0 \le j < M$) goes from node $U[j]$ to node $V[j]$ and has length $D[j]$.

For the tourist Dundun, an ideal sightseeing route should satisfy the following conditions:

• It is a simple path from node $0$ to node $N - 1$.
• It is a colored path, meaning that all nodes on the path have pairwise distinct color labels.
• The number of nodes on the path is less than or equal to $L$.

More specifically, an ideal sightseeing route is a sequence of nodes, such as $(t_0, t_1, \cdots, t_{q-1})$, that satisfies all of the following:

• For each $i$ ($0 \le i < q - 1$), there exists a directed edge from node $t_i$ to node $t_{i+1}$.
• $t_0 = 0$ and $t_{q-1} = N - 1$.
• For every pair $i, j$ ($0 \le i < j < q$), we have $C[t_i] \ne C[t_j]$.
• $q \le L$.

The length of a path is defined as the sum of the lengths of its edges. Your task is to find the longest sightseeing route that satisfies all of Dundun’s requirements.

Input Format

Read input from standard input.

The input has five lines.

The first line contains four positive integers $N, M, L$ and $K$, representing the number of nodes, the number of edges, the upper limit on the number of nodes in an ideal sightseeing route, and the range of color labels.

The second line contains $N$ integers $C[0], C[1], \cdots, C[N - 1]$, representing the color label of each node.

Next comes the edge information.

The third line contains $M$ integers $U[0], U[1], \cdots, U[M - 1]$, representing the starting node of each directed edge.

The fourth line contains $M$ integers $V[0], V[1], \cdots, V[M - 1]$, representing the ending node of each directed edge.

The fifth line contains $M$ integers $D[0], D[1], \cdots, D[M - 1]$, representing the length of each directed edge.

The input guarantees that there is no edge whose start and end are the same, such as $(u, u)$. Each directed edge $(u, v)$ appears at most once, but it is possible that both $(u, v)$ and $(v, u)$ exist at the same time.

Output Format

Write to standard output.

Output one number, representing the maximum length of an ideal sightseeing route.

6 9 4 10
0 2 2 3 3 9
0 0 0 1 1 1 2 3 4
1 2 4 3 4 5 4 5 5
1 2 4 3 2 8 5 3 1

9

Hint

Sample Explanation

Below is the sample graph, where the black and red numbers represent node indices and edge lengths, respectively.

:::align{center} :::

As shown in the table below, under the restriction of using no more than four nodes, there are five colored paths from node $0$ to node $5$. The longest one is $(0, 1, 5)$, with length $9$.

Colored Path	Number of Nodes	Length
$(0, 1, 3, 5)$	$4$	$7$
$(0, 1, 4, 5)$	^	$4$
$(0, 2, 4, 5)$		$8$
$(0, 1, 5)$	$3$	$9$
$(0, 4, 5)$	^	$5$

Subtasks

$20\%$ of the testdata satisfies: for every $i$ ($0 \le i < N - 1$), $C[i] \le C[i + 1]$, and for every $j$ ($0 \le j < M$), $U[j] < V[j]$.

Another $30\%$ of the testdata satisfies: $K \le 15$.

All testdata satisfies:

• $2 \le N \le 100$
• $1 \le M \le 5000$
• $2 \le L \le 9 \le K \le 30$
• $C[0] = 0$ and $C[N - 1] = K - 1$
• For each $i$ ($1 \le i \le N - 2$)：

$$\begin{aligned} &1 \le C[i] \le K - 2 \end{aligned}$$

• For each $j$ ($0 \le j < M$)：

$$\begin{aligned} &0 \le U[j], V[j] < N \\ &C[U[j]] \ne C[V[j]] \\ &1 \le D[j] \le 10^6 \end{aligned}$$

• There is at least one colored path from node $0$ to node $N - 1$ with no more than $L$ nodes.

Translated by ChatGPT 5