Description

题目描述

给你一张有向图，每个点有一个点权。任意时刻你可以任意选择一个有入度的点，获得它的点权并把它和它的出边从图上删去。最多能选择 $k$ 个点，求最多能获得多少点权。

格式

输入格式

输入的第一行是三个用空格隔开的整数，代表图的点数 $n$ 和边数 $m$ 以及点数的限制 $k$。

输入的第二行是 $n$ 个用空格隔开的整数，第 $i$ 个数 $w_i$ 代表点 $i$ 的点权。

第 $3$ 到第 $(m + 2)$ 行，每行两个用空格隔开的整数 $u, v$，代表一条 $u$ 指向 $v$ 的有向边。

输出格式

输出一行一个整数，代表最大的点权。

样例

输入样例：

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

输出样例：

24

Hint

样例输入输出 1 解释 选择 $3, 5, 7$ 三个节点。 对于全部的测试点，保证 $1 \leq n \leq 5 \times 10^5$，$1 \leq m \leq 2 \times 10^6$，$0 \leq w_i \leq 10^3$，$0 \leq k \leq n$。