著名的魔术师博里亚·布迪尼（Borya Budini）在 $X$ 国旅行，该国由 $n$ 个城市组成。

然而，不幸发生了，他在 1 号城市被抢劫了。现在，布迪尼面临着回到 $n$ 号城市家中的艰难旅程。

他打算乘飞机回家。该国共有 $m$ 个航班，第 $i$ 个航班从 $a_i$ 飞往 $b_i$，票价为 $s_i$。为了乘坐该航班，博里亚必须位于城市 $a_i$，并且手里至少有 $s_i$ 卢布（他将把这些钱花在飞行上）。

在被抢劫后，他只剩下 $p$ 卢布，但他并没有绝望！在城市 $i$ 时，他每天都可以组织表演，每次表演可以为他带来 $w_i$ 卢布的收入。

请帮助魔术师确定他是否能回到家，以及为了回家他最少需要组织多少次表演。

输入格式

第一行包含四个整数 $n, m, p$ 和 $g$（$2 \le n \le 800$，$1 \le m \le 3000$，$0 \le p \le 10^9$，$0 \le g \le 6$）—— 分别表示城市的数量、航班的数量、初始的卢布数量和测试点组的编号。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 10^9$）—— 表示在各个城市进行表演的收益。

接下来的 $m$ 行，每行包含三个整数 $a_i, b_i$ 和 $s_i$（$1 \le a_i, b_i \le n$，$1 \le s_i \le 10^9$）—— 分别表示第 $i$ 个航班的起点城市、终点城市以及票价。

输出格式

输出一个整数 —— 博里亚为了回家最少需要组织的表演次数。如果无法回家，则输出 $-1$。

样例

输入样例 1

4 4 2 0
7 4 3 1
1 2 21
3 2 6
1 3 8
2 4 11

输出样例 1

4

输入样例 2

4 4 10 0
1 2 10 1
1 2 20
2 4 30
1 3 25
3 4 89

输出样例 2

24

输入样例 3

4 4 7 0
5 1 6 2
1 2 5
2 3 10
3 4 50
3 4 70

输出样例 3

10

输入样例 4

4 1 2 0
1 1 1 1
1 3 2

输出样例 4

-1

说明

在第一个样例中，博里亚的最佳方案是在第一个城市进行 $4$ 次表演，最终拥有 $2 + 7 \cdot 4 = 30$ 卢布，然后沿着路线 $1 - 3 - 2 - 4$ 前行，花费 $6 + 8 + 11 = 25$ 卢布。

在第二个样例中，博里亚的最佳方案是在第一个城市进行 $15$ 次表演，飞往第 $3$ 个城市，在那里进行 $9$ 次表演，然后前往第 $4$ 个城市。

子任务

该题的测试点分为 6 组。每组的分数只有在通过该组的所有测试点以及某些先前组的所有测试点时才能获得。请注意，某些组不需要通过样例测试。Offline 测试意味着该组的测试结果将在比赛结束后才可用。