← 返回题目列表

Codeforces · 1863/E

E. 极速奔跑

中文机器翻译题面 查看原题

您正在玩电子游戏。游戏有 $$$n$$$ 任务需要完成。然而,第 $$$j$$$ 个任务只能在游戏日 $$$h_j$$$ 小时开始时完成。比赛日长达 $$$k$$$ 小时。每个比赛日的时间编号为 $$$0, 1, \ldots, k - 1$$$。第一天结束后,新的一天开始,依此类推。

另外,任务之间存在依赖关系,也就是说,对于某些 $$$(a_i, b_i)$$$ 配对,第 $$$b_i$$$ 个任务只能在第 $$$a_i$$$ 个任务之后完成。保证不存在循环依赖,否则游戏将是无与伦比的,没有人会玩。

你有足够的技能在可忽略不计的时间内完成任意数量的任务(即你可以在同一小时开始时完成任意数量的任务,即使它们之间存在依赖关系)。你想尽快完成所有任务。为此,您可以按任何有效顺序完成任务。完成时间等于完成最后一个任务的时间与完成第一个任务的时间之差。

找出完成游戏所需的最短时间。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le 100\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1\le n\le 200\,000$$$, $$$0\le m\le 200\,000$$$, $$$1\le k\le 10^9$$$) —分别是任务、任务之间的依赖关系数量以及游戏日的小时数。

下一行包含 $$$n$$$ 整数 $$$h_1, h_2, \ldots, h_n$$$ ($$$0\le h_i < k$$$)。

接下来的 $$$m$$$ 行描述了依赖关系。这些行的第 $$$i$$$ 包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1\le a_i < b_i\le n$$$) 意味着任务 $$$b_i$$$ 只能在任务 $$$a_i$$$ 之后完成。保证所有依赖关系都是成对不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,输出一个整数 - 最短完成时间。

示例

输入 #1

6
4 4 24
12 16 18 12
1 2
1 3
2 4
3 4
4 3 10
2 6 5 9
1 4
2 4
3 4
2 1 10
5 5
1 2
5 0 1000
8 800 555 35 35
5 0 10
3 2 5 4 7
3 2 5
4 3 2
1 2
2 3

输出 #1

24
7
0
480
5
8

注意

在第一个测试用例中,任务 $$$1$$$ 和 $$$4$$$ 必须在当天的第 $$$12$$$ 小时开始时完成,但它们不能在同一个小时内完成,因为您还需要在它们之间完成任务 $$$2$$$ 和 $$$3$$$。不过,您可以在 $$$24$$$ 小时内完成所有这些。为此,您需要在第一个游戏日的 $$$12$$$ 小时内完成第一个任务。在 $$$16$$$ 小时内完成任务 $$$2$$$。在 $$$18$$$ 小时内完成任务 $$$3$$$。最后在第二天的$$$12$$$小时你可以完成任务$$$4$$$。已用总时间(从完成第一个任务到完成最后一个任务的那一刻)为 $$$24$$$ 小时。

在第三个测试用例中,您可以完成第一个任务,然后立即完成剩余的任务。您可以在第一天的 $$$5$$$ 小时开始完成第一个任务。在此之后,第二个任务可用,您也可以完成它。已用总时间为 $$$0$$$。

在第四个测试用例中,您可以从第三个任务开始。第一天的 $$$555$$$ 小时开始,第二天的 $$$35$$$ 小时结束。总共花费的时间为$$$1035-555=480$$$。