著名的魔术师博里亚·布迪尼在由 n 个城市组成的国家 X 中旅行。然而不幸的是，他在城市 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, \ldots, 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。

OOI