#6706. 西湖观光

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: SilveryStar

题目描述

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} 一行人能取得的最大心情值。

样例

样例输入

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

样例输出

18

数据范围与提示

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