题目来自第 32 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 512 MB

题目描述

西西艾弗岛的路线图可以看作是一个具有 $n$ 个节点和 $m$ 条有向边的图。 第 $i$ 个节点（$0 \leq i < n$）有一个颜色标签 $c_i \in \{0, 1, \cdots, k-1\}$，第 $j$ 条边（$0 \leq j < m$）从节点 $u_j$ 指向节点 $v_j$，长度为 $d_j$。

对于游客顿顿来说，理想的观光路线应满足以下条件：

• 是一条从节点 $0$ 到节点 $n-1$ 的简单路径；
• 是一条彩色路径，即路径上每个节点的颜色标签均不相同；
• 并且包含的节点数小于或等于 $l$。

具体而言，理想的观光路线是一个节点序列，例如 $(t_0, t_1, \cdots, t_{q-1})$，满足以下所有要求：

• 对于每个 $i$（$0 \leq i < q-1$），存在一条从节点 $t_i$ 到节点 $t_{i+1}$ 的有向边。
• $t_0 = 0$ 且 $t_{q-1} = n-1$
• 对于每对 $i, j$（$0 \leq i < j < q$），都有 $c_{t_i} \neq c_{t_j}$。
• $q \leq l$

一条路径的长度定义为边的总长度。你的任务是找到满足游客顿顿所有要求的最长观光路线。

输入格式

从标准输入读入数据。

输入共五行。

输入的第一行包含四个正整数 $n, m, l, k$，分别表示图的节点数、边数、理想观光路线的节点数上限和颜色标签范围。

输入的第二行包含 $n$ 个整数 $c_0, c_1, \cdots, c_{n-1}$，表示图中每个节点的颜色标签。

接下来输入边的信息。

输入的第三行包含 $m$ 个整数 $u_0,u_1, \cdots, u_{m-1}$，表示每条有向边的起点；

输入的第四行包含 $m$ 个整数 $v_0, v_1, \cdots, v_{m-1}$，表示每条有向边的终点；

输入的第五行包含 $m$ 个整数 $d_0, d_1, \cdots, d_{m-1}$，表示每条有向边的长度。

输入数据保证不存在起点终点相同的边，如 $(u, u)$；每条有向边 $(u, v)$ 仅会出现一次，但不排除 $(u, v)$ 和 $(v, u)$ 可能同时存在。

输出格式

输出到标准输出。

输出一个数，表示理想观光路线的最大长度。

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

样例解释

以下是示例图，其中黑色和红色数字分别表示节点编号和边的长度。

如下表所示，在不超过四个节点的限制下，共有五条从节点 $0$ 到节点 $5$ 的彩色路径。其中最长的一条是 $(0, 1, 5)$，长度为 $9$。

子任务

全部的测试数据满足：

• $2\le n\le 100$
• $1\le m\le 5000$
• $2\le l\le 9\le k\le 30$
• $c_0=0,c_{n-1} = k-1$
• $\forall\ i\ (1\le i\le n - 2),\ 1 \leq c_i \leq k-2$
• $\forall\ j\ (0\le j<m),\ 0\le u_j,v_j<n,\ c_{u_j}\ne c_{v_j},\ 1\le d_j\le 10^6$
• 至少存在一条从节点 $0$ 到节点 $n-1$ 的彩色路径，节点数不超过 $l$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。