[yLOI2018] 锦鲤抄

> 你在尘世中辗转了千百年， > 却只让我看你最后一眼。 > 火光描摹容颜燃尽了时间， > 别留我一人，孑然一身，凋零在梦境里面。 —— 银临 & 云の泣《锦鲤抄》 本题原名《逛庭院》。 这首歌的文案如下：（注：不阅读文案不影响下面的阅读） > 宁武皇仁光九年锦文轩刻本《异闻录》载：扶桑画师浅溪，居泰安，喜绘鲤。院前一方荷塘，锦鲤游曳，溪常与嬉戏。 > 其时正武德之乱，藩镇割据，战事频仍，魑魅魍魉，肆逆于道。兵戈逼泰安，街邻皆逃亡，独溪不舍锦鲤，未去。 > 是夜，院室倏火。有人入火护溪，言其本鲤中妖，欲取溪命，却生情愫，遂不忍为之。翌日天明，火势渐歇，人已不见。 > 溪始觉如梦，奔塘边，但见池水干涸，莲叶皆枯，塘中鲤亦不知所踪。 > 自始至终，未辨眉目，只记襟上层迭莲花，其色魅惑，似血着泪。 > 后有青岩居士闻之，叹曰：魑祟动情，必作灰飞。犹蛾之投火耳，非愚，乃命数也。

扶苏被画师和锦鲤的故事深深地打动了。为了能让锦鲤和画师继续生活在一起，他决定回到着火的庭院中灭掉大火。 画师的庭院可以抽象成一个有向图，每个点代表着一个着火的位置。为了量化火势的大小，扶苏给每个点一个火力值，火力值越大，代表这个点的火势越强。 风助火势，火借风力，对于每一个着火点，都有可能因为大风使得火扩散到其他点。有向图的每条边 $<u,v>$ 代表大火是从点 $u$ 扩散到点 $v$ 的。需要注意的是一个点可能会扩散到很多点，也可能是由很多点的大火一起扩散成的。 为了不因为灭掉火源让画师发现有人在帮他灭火，在任意时刻，扶苏不能灭掉任何一个不被任何点所扩散的点的火。一个点的火被灭掉后，所代表该点的火扩散的所有边将消失。需要说明的是，虽然边消失了，但是该点扩散到的所有点属性除入度以外都不会改变，更不会消失。 因为穿越的时间有限，扶苏只能灭掉最多 $k$ 个点的火。他想问问你他最多能扑灭多少火力值。 #### 简化版题意： 给你一张有向图，每个点有一个点权。任意时刻你可以任意选择一个**有入度**的点，获得它的点权并把它和它的出边从图上删去。最多能选择 $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

### 样例输入输出 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$ 的末位数字可以帮助你快速的判断测试点所在的子任务。