题目描述

2020 年 10 月 7 日，$\text{Jary}$ 与她的同学们结束了为期七天的 $\text{qblt}$ 的集训，决定到西湖周围游玩一番。

在坐的士前往西湖的路上， $\text{Jary}$ 不禁想起去年学长们的经历，特意提前找来了西湖的旅游地图决定好好计划一番。

$\text{Jary}$ 发现西湖附近共有 $n$ 处景点，景点与景点之间有 $m$ 条单向的道路，第 $i$ 条道路的长度为 $dis_i$，到达西湖后，她们将从第 $s$ 处景点出发，并在游览完第 $t$ 处景点后踏上回宾馆的路。

「嗯……还得考虑不同景点的风景和我们的精力」 $\text{Jary}$ 喃喃道。

根据网络上的评价， $\text{Jary}$ 给不同的景点设定了一个观赏值 $val_i$ ，由于景区中需要徒步行走，同学们也会不断消耗体力， $\text{Jary}$ 认为消耗的体力是途径的所有道路的长度之和。

「太疲倦的话，大概就没心情欣赏美景了吧」

采纳了同学们的建议，大家一致认为当消耗了 $sum$ 的体力后，欣赏第 $u$ 处景点只能增加 $\left\lceil\frac{val_{ u }}{sum}\right\rceil$ 点心情值。

$\text{Jary}$ 还发现景区中各处都配有观光车，但是她们带的钱只够乘坐 $k$ 次，在车上同学们可以有一定时间休息，换句话说，坐车经过一条长为 $dis_i$ 的道路，会使 $sum$ 减少 $dis_i$（ $sum$ 初始为 $1$ ，若减少后小于 $1$ 也视为 $1$ ），现在 $\text{Jary}$ 想知道怎样安排行程才能得到尽可能多的心情值，你需要帮她求出这个最大值。

输入格式

第一行包含五个整数 $n,\,m,\,k,\,s,\,t$ ，含义见题面。

第二行包含 $n$ 个整数，第 $i$ 个数表示第 $i$ 个景点的观赏值 $val_i$。

下面 $m$ 行，每行三个整数 $u,\,v,\,w$ ，表示景点 $u,\,v$ 直接有一条长度为 $w$ 的单向道路，数据保证所有边不成环。

输出格式

输出包含一个数，表示 $\text{Jary}$ 一行人能取得的最大心情值。

样例

input

7 8 1 1 7
5 7 2 8 3 4 6
1 2 4
1 3 3
1 5 1
2 4 1
3 6 2
4 7 2
5 7 7
6 7 5

output

18

数据范围与提示

对于 $100\%$ 的数据，保证 $n\le200,\;m\le500,\;k\le5,\;\sum dis_i\le10^4$