他要乘飞机到达那里。该国总共有 $$$m$$$ 航班,第 $$$i$$$ 从城市 $$$a_i$$$ 飞往城市 $$$b_i$$$,费用为 $$$s_i$$$ 硬币。请注意,第 $$$i$$$ 航班是单程航班,因此不能用于从城市 $$$b_i$$$ 飞往城市 $$$a_i$$$。要使用它,Borya 必须位于 $$$a_i$$$ 城市,并且至少拥有 $$$s_i$$$ 硬币(他将在航班上花费)。
抢劫后,他只剩下$$$p$$$硬币,但他并不绝望!在城市$$$i$$$里,他每天都可以组织演出,每次演出都会给他带来$$$w_i$$$金币。
帮助魔术师了解他是否能够回家,以及他必须组织的最少表演次数是多少。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 80$$$) – 测试用例的数量。测试用例的描述如下。
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$p$$$ ($$$2 \le n \le 800$$$, $$$1 \le m \le 3000$$$, $$$0 \le p \le 10^9$$$) — 城市数量、航班数量和初始金币数量。
第二行包含 $$$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$$$ 航班。
保证所有测试用例的$$$n$$$总和不超过$$$800$$$,所有测试用例的$$$m$$$总和不超过$$$10000$$$。
输出
对于每个测试用例,打印一个整数 - Borya 必须组织回家的最少表演次数,如果无法做到这一点,则打印 $$$-1$$$。
示例
输入 #1
4 4 4 2 7 4 3 1 1 2 21 3 2 6 1 3 8 2 4 11 4 4 10 1 2 10 1 1 2 20 2 4 30 1 3 25 3 4 89 4 4 7 5 1 6 2 1 2 5 2 3 10 3 4 50 3 4 70 4 1 2 1 1 1 1 1 3 2
输出 #1
4 24 10 -1
注意
在第一个例子中,Borya 最好在第一个城市进行 $$$4$$$ 表演,获得 $$$2 + 7 \cdot 4 = 30$$$ 硬币,然后沿着路线 $$$1-3-2-4$$$ 行走,花费 $$$6+8+11=25$$$ 硬币。 在第二个示例中,Borya 的最佳选择是在第一个城市进行 $$$15$$$ 表演,飞往 $$$3$$$ 城市,在那里进行 $$$9$$$ 表演,然后前往 $$$4$$$ 城市。