P15403 [NOISG 2026 Prelim] Mushroom Ring（暂无数据）

在野外，蘑菇常常成环形、弧形或其他形状生长。尽管它们自然出现，但蘑菇环长期以来一直是神话和民间传说的主题。有人说它们是被龙尾烧焦的土地上长出来的。另一个传说称女巫夜间会在它们周围跳舞。最近，有传说称天才们会聚集到蘑菇环，站在中心，构思出六个关于采集蘑菇的编程竞赛题。 蜗牛斯图亚特在无限的原野上旅行后，现在居住在蜗牛村，村里有一圈 $n$ 个巨大的蘑菇！蘑菇编号为 1 到 $n$。在每个蘑菇旁边，有指向其他所有蘑菇的 $n-1$ 个路标，总共有 $n(n-1)$ 个路标。 有些路标上写着 $m$ 个连续的数字范围。在放在蘑菇 $u[i]$ 旁边并指向蘑菇 $v[i]$ 的路标上，写着 **从 $a[i]$ 到 $b[i]$ 的所有整数**（$1 \le a[i] \le b[i] \le n$，$1 \le i \le m$）。这些路标满足以下两条清晰规则： 1. 一个路标不能包含其所在蘑菇的编号。形式化地说，$u[i] < a[i]$ 或 $b[i] < u[i]$。 2. 位于同一个蘑菇旁边的两个路标上的范围不能包含相同的数字。形式化地说，如果 $i \ne j$ 且 $u[i] = u[j]$，则 $b[i] < a[j]$ 或 $b[j] < a[i]$。 注意，对 $v[i]$ 没有限制。 蜗牛能够完美地遵循路标上的指示。假设一只蜗牛当前在蘑菇 $c$，最终想要到达蘑菇 $d$。如果 $c = d$，她就完成了。否则，她会查看蘑菇 $c$ 旁边的路标，找到包含数字 $d$ 的那个路标，然后沿着该路标指向的下一个蘑菇 $v[i]$ 移动，并重复这个过程。 不幸的是，路标本身可能不完美。如果蜗牛在任何路标上都找不到目标蘑菇 $d$，她就会卡住，无法前进。另一方面，路标可能使蜗牛陷入无限循环，永远不经过蘑菇 $d$。 定义路标的 **效用** 为有序对 $(s, d)$ 的数量，使得从蘑菇 $s$ 出发的蜗牛可以通过跟随路标到达蘑菇 $d$。 斯图亚特想要改进路标以最大化效用。由于资源有限，最多可以进行 $k$ 次路标编辑。编辑有两种类型：向路标添加一个数字，或删除一个现有数字。编辑后，两条清晰规则必须仍然满足。编辑后的路标上的数字不一定需要是连续的范围。 帮助斯图亚特找出在最优编辑后可能的最大效用。

你的程序必须从标准输入中读取数据。 输入的第一行包含三个以空格分隔的整数 $n$、$m$ 和 $k$，分别描述蘑菇的数量、范围的数量以及允许的最大编辑次数。 接下来的 $m$ 行，每行包含四个以空格分隔的整数。第 $i$ 行包含 $u[i]$、$v[i]$、$a[i]$ 和 $b[i]$，表示初始时，在蘑菇 $u[i]$ 旁边指向蘑菇 $v[i]$ 的路标上，写着从 $a[i]$ 到 $b[i]$ 的第 $i$ 个连续数字范围。

你的程序必须输出到标准输出。 输出一个整数，即在进行最多 $k$ 次自由编辑后可能的最大效用。

#### 样例测试用例 1 解释 下图展示了村庄中的蘑菇和非空路标。 假设一只蜗牛想从蘑菇 6 移动到蘑菇 2。她找到包含数字 2 的路标，该路标指向蘑菇 1，于是她移动到那里。由于她还没到蘑菇 2，她再次找到包含数字 2 的路标。这次它指向蘑菇 2，于是她移动到那里。因此，她可以通过跟随路标成功到达蘑菇 2。 有序对 $(s, d)$ 为 $(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (1, 2),$ 和 $(6, 2)$。效用为 8。由于 $k = 0$，无法进行编辑，因此答案为 8。 :::align{center}  ::: #### 样例测试用例 2 解释 路标初始与样例测试用例 1 相同。我们可以进行 $k = 1$ 次编辑。 一个最优解是向蘑菇 5 旁边指向蘑菇 6 的路标添加数字 2。除了样例测试用例 1 中的 8 个有序对 $(s, d)$ 之外，我们还得到 $(4, 2)$ 和 $(5, 2)$。效用为 10。 :::align{center}  ::: #### 样例测试用例 3 解释 路标初始与样例测试用例 1 相同。我们可以进行 $k = 2$ 次编辑。 一个最优解是删除蘑菇 6 旁边指向蘑菇 1 的路标上的数字 3，并向蘑菇 6 旁边指向蘑菇 3 的路标添加数字 3。这使得蜗牛可以从任何蘑菇出发，通过路标移动到蘑菇 3。效用为 13。 :::align{center}  ::: #### 子任务 对于所有测试用例，输入均满足以下范围： - $2 \le n \le 150000$ - $1 \le m \le 300000$ - $0 \le k \le 10^{12}$ - 对于所有 $1 \le i \le m$，$1 \le u[i], v[i] \le n$ 且 $u[i] \ne v[i]$ - 对于所有 $1 \le i \le m$，$1 \le a[i] \le b[i] \le n$ - 对于所有 $1 \le i \le m$，$u[i] < a[i]$ 或 $b[i] < u[i]$ - 如果 $i \ne j$ 且 $u[i] = u[j]$，则 $b[i] < a[j]$ 或 $b[j] < a[i]$ 你的程序将在满足以下限制的输入实例上进行测试： | 子任务 | 分值 | 附加约束 | |:------:|:----:|:--------:| | 0 | 0 | 样例测试用例 | | 1 | 6 | $n \le 200, m \le 400, k = 0$ | | 2 | 6 | $n \le 1500, m \le 3000, k = 0$ | | 3 | 22 | $n \le 1500, m \le 3000, k \le 10$ | | 4 | 11 | $n \le 1500, m \le 3000, k \le 1000$ | | 5 | 7 | $n \le 1500, m \le 3000$ | | 6 | 20 | $n \le 30000, m \le 60000, k = 0$ | | 7 | 15 | $n \le 30000, m \le 60000$ | | 8 | 13 | 无额外约束 | 翻译由 DeepSeek 完成