You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

鸡煲正处于“高塔”的一层，这一层由 $N$ 个房间和 $M$ 条单向通道组成。每个房间 $i$ 都有价值为 $V_i$ 的宝箱，鸡煲每次经过房间都可以获得一次这个房间的宝箱，在每个通道中都有可怕的怪物，经过第 $i$ 个通道会鸡煲减少 $W_i$ 点生命值。 你需要从指定起点 $s$ 出发，最后回到 $s$ ，在高塔中带出的价值尽可能多。

形式化的说： 给定一个有向带权图 $G = (V, E)$，其中 $|V| = n, |E| = m$。每个顶点 $i \in V$ 拥有一个点权 $V_i \in \mathbb{Z}^+$ ，每条边 $e = (u, v) \in E$ 拥有一个边权 $w_e \in \mathbb{Z}^+$ ，给定初始生命值 $H \in \mathbb{Z}^+$ 和起点 $s \in V$。

定义合法路径 $P$ 是一个顶点序列 $(v_0, v_1, v_2, \dots, v_k)$满足：

• $v_0 = v_k = s$。
• 对于所有 $0 \le i < k$，存在有向边 $(v_i, v_{i+1}) \in E$。
• 路径上所有边的权值之和必须小于 $H$，即：$\sum_{i=0}^{k-1} w_{v_i, v_{i+1}} \le H - 1$

求 $\max({\sum^{k}_{i=0}V_i})$

Input Format

第一行输入 $n , m , h ,s$ 分别为房间数，边数，生命值，起点。 第二行包含 $n$ 个整数，表示每个房间中宝箱的价值 $V_i$。 接下来 $m$ 行，每行三个整数 $u, v, c$，表示从房间 $u$ 到房间 $v$ 有一条消耗 $c$ 个血量的有向边。

Output Format

输出一个整数，表示在回到 $s$ 时能获得的最大总价值。

Sample

Input

2 2 3 1
5 10
1 2 2
2 1 2

Output

5

Hint

$1\le s,u,v \le n \le 1e3$, $1\le m \le 1e4$, $1 \le h,c \le 1e3$, $1 \le V_i \le 1e9$