洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。
西西艾弗岛的路线图可以看作是一个具有 个节点和 条有向边的图。第 个节点（）有一个颜色标签 ，第 条边（）从节点 指向节点 ，长度为 。
对于游客顿顿来说，理想的观光路线应满足以下条件：
具体而言，理想的观光路线是一个节点序列，例如 ，满足以下所有要求：
一条路径的长度定义为边的总长度。你的任务是找到满足游客顿顿所有要求的最长观光路线。
从标准输入读入数据。
输入共五行。
输入的第一行包含四个正整数 、、 和 ，分别表示图的节点数、边数、理想观光路线的节点数上限和颜色标签范围。
输入的第二行包含 个整数 ，表示图中每个节点的颜色标签。
接下来输入边的信息。
输入的第三行包含 个整数 ，表示每条有向边的起点；
输入的第四行包含 个整数 ，表示每条有向边的终点；
输入的第五行包含 个整数 ，表示每条有向边的长度。
输入数据保证不存在起点终点相同的边，如 ；每条有向边 仅会出现一次，但不排除 和 可能同时存在。
输出到标准输出。
输出一个数，表示理想观光路线的最大长度。
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
以下是示例图，其中黑色和红色数字分别表示节点编号和边的长度。
:::align{center} :::
如下表所示，在不超过四个节点的限制下，共有五条从节点 到节点 的彩色路径。其中最长的一条是 ，长度为 。
的测试数据满足：对于每个 （），有 ，以及对于每个 （），有 。
另有 测试数据满足：。
全部的测试数据满足：
:::