题目描述

在野外，蘑菇常常成环形、弧形或其他形状生长。尽管它们自然出现，但蘑菇环长期以来一直是神话和民间传说的主题。有人说它们是被龙尾烧焦的土地上长出来的。另一个传说称女巫夜间会在它们周围跳舞。最近，有传说称天才们会聚集到蘑菇环，站在中心，构思出六个关于采集蘑菇的编程竞赛题。

蜗牛斯图亚特在无限的原野上旅行后，现在居住在蜗牛村，村里有一圈 $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$ 次自由编辑后可能的最大效用。

6 7 0
1 2 2 3
2 5 3 3
2 5 6 6
4 5 2 3
5 4 1 1
5 6 3 3
6 1 2 5

8

6 7 1
1 2 2 3
2 5 3 3
2 5 6 6
4 5 2 3
5 4 1 1
5 6 3 3
6 1 2 5

10

6 7 2
1 2 2 3
2 5 3 3
2 5 6 6
4 5 2 3
5 4 1 1
5 6 3 3
6 1 2 5

13

提示

样例测试用例 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]$

你的程序将在满足以下限制的输入实例上进行测试：

翻译由 DeepSeek 完成