灰色外星人 E.T. 喜欢玩《原神》，但他不太擅长这个游戏。他目前正在尝试解决稻妻区域的一个方块机关谜题，但已经卡了几个小时。他现在请求你帮助他解决它。

图 I.1：方块机关谜题

图 I.2：玩家击打方块机关

解密区域散落着 $n$ 个方块，编号为 $1$ 到 $n$。每个方块上都有一朵有 $k$ 片花瓣的花。在任何时候，一个方块亮起的花瓣数量可以在 $1$ 到 $k$ 之间。当玩家击打一个方块时，亮起的花瓣数量会增加 $1$ —— 除非所有 $k$ 片花瓣都已经亮起，在这种情况下，方块会重置为只有 $1$ 片花瓣亮起。当每个方块的所有 $k$ 片花瓣都亮起时，谜题就被解决了。

某些方块对之间存在从一个方块到另一个方块的单向连锁反应：击打一个方块也会增加另一个方块上亮起的花瓣数量，但反之则不然。对于任何这种从方块 $a$ 到方块 $b$ 的连锁反应（击打方块 $a$ 会同时增加方块 $a$ 和方块 $b$ 上亮起的花瓣数量），方块编号必须满足 $a < b$，这意味着所有的连锁反应都是从编号较小的方块指向编号较大的方块。请注意，如果存在从方块 $a$ 到方块 $b$ 的连锁反应，以及从方块 $b$ 到方块 $c$ 的另一个连锁反应，击打方块 $a$ 并不会影响方块 $c$（除非直接存在从方块 $a$ 到方块 $c$ 的另一个连锁反应）。

E.T. 想知道他最少需要击打方块多少次才能解决这个谜题。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$0 \le m \le 5 \cdot 10^5$，$m \le \frac{n(n-1)}{2}$，$1 \le k \le 10^9$），分别表示方块的数量、单向连锁反应的数量以及每个方块的花瓣数量。

接下来的 $n$ 行，每行包含一个整数。第 $i$ 行的整数表示方块 $i$ 初始亮起的花瓣数量。所有这些整数都在 $1$ 到 $k$ 之间（含 $1$ 和 $k$）。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a < b \le n$），描述从方块 $a$ 到方块 $b$ 的单向连锁反应。所有连锁反应都是唯一的。

输出格式

输出一个整数，表示外星人 E.T. 解决谜题所需的最少击打次数。如果该谜题无法解决，则输出 $-1$。

样例

样例输入 1

5 3 10
8
9
6
9
6
1 2
2 3
2 4

样例输出 1

22

样例说明 1

我们可以通过 22 次击打来解决这个谜题：

1. 击打方块 5 共 4 次。此时，方块 5 有 10 片亮起的花瓣。
2. 击打方块 2 共 9 次。此时，方块 2 有 8 片亮起的花瓣，方块 3 有 5 片，方块 4 有 8 片。
3. 击打方块 3 共 5 次。此时，方块 3 有 10 片亮起的花瓣。
4. 击打方块 1 共 2 次。此时，方块 1 和方块 2 都有 10 片亮起的花瓣。注意，击打方块 1 不会增加方块 3 或方块 4 上亮起的花瓣数量。
5. 击打方块 4 共 2 次。此时，所有方块都有 10 片亮起的花瓣。