Description

扶苏被画师和锦鲤的故事深深地打动了。为了能让锦鲤和画师继续生活在一起，他决定回到着火的庭院中灭掉大火。

画师的庭院可以抽象成一个有向图，每个点代表着一个着火的位置。为了量化火势的大小，扶苏给每个点一个火力值，火力值越大，代表这个点的火势越强。

风助火势，火借风力，对于每一个着火点，都有可能因为大风使得火扩散到其他点。有向图的每条边 $<u,v>$ 代表大火是从点 $u$ 扩散到点 $v$ 的。需要注意的是一个点可能会扩散到很多点，也可能是由很多点的大火一起扩散成的。

为了不因为灭掉火源让画师发现有人在帮他灭火，在任意时刻，扶苏不能灭掉任何一个不被任何点所扩散的点的火。一个点的火被灭掉后，所代表该点的火扩散的所有边将消失。需要说明的是，虽然边消失了，但是该点扩散到的所有点属性除入度以外都不会改变，更不会消失。

因为穿越的时间有限，扶苏只能灭掉最多 $k$ 个点的火。他想问问你他最多能扑灭多少火力值。

简化版题意：

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

Input Format

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

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

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

Output Format

输出一行一个整数，代表最大的火力值。

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$ 三个节点。

数据规模与约定

本题采用多测试点捆绑测试，共有 $5$ 个子任务。

• Subtask 1（30 points）：$n = 10$，$m = 50$。
• Subtask 2（30 points）：$n = 100001$，$m = 500001$。保证给出的图是一个有向无环图。
• Subtask 3（20 points）：$n = 100002$，$m = 500002$。保证给出的图中，没有入度的点有且仅有一个。
• Subtask 4（17 points）：$n = 100003$，$m = 500003$。
• Subtask 5（3 points）：$n = 500004$，$m = 2000004$。

对于全部的测试点，保证 $1 \leq n \leq 5 \times 10^5 + 4$，$1 \leq m \leq 2 \times 10^6 + 4$，$0 \leq w_i \leq 10^3$，$0 \leq k \leq n$。

不保证给出的图没有自环。

提示

• 请注意数据读入对程序效率造成的影响。
• $n$ 的末位数字可以帮助你快速的判断测试点所在的子任务。