在野外，人们经常能看到蘑菇长成圈状、弧状或其他形状。虽然它们是自然生长的，但“蘑菇圈”尤其长期以来一直是神话和民间传说的题材。据说，当土地被龙尾烧焦时，它们就会从土地中生长出来。另一个神话称，女巫会在夜间围绕着它们跳舞。最近，传说中提到一些天才聚集在蘑菇圈旁，站在中心，构思出了六道关于收集蘑菇的程序设计竞赛题目。

在无尽原野上旅行之后，蜗牛 Stuart 现在居住在蜗牛村，这里由一圈共 $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. 指示牌不能包含它所在的蘑菇的编号。形式化地，对于任意 $i$，有 $u[i] < a[i]$ 或 $b[i] < u[i]$。
2. 放在同一个蘑菇旁的指示牌上的两个区间不能包含相同的数字。形式化地，如果 $i \neq 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$。

Stuart 想要改进指示牌以最大化效用值。由于资源匮乏，最多只能对指示牌进行 $k$ 次修改。修改有两种类型：在指示牌上添加一个新数字，或者删除一个已有的数字。在进行修改后，两条清晰度规则必须仍然满足。修改后，指示牌上包含的数字不一定需要是连续的区间。

帮助 Stuart 找到在进行最优修改后，可能达到的最大效用值。

输入格式

程序必须从标准输入读入。

输入的第一行包含三个空格分隔的整数 $n$、$m$ 和 $k$，分别表示蘑菇的数量、区间的数量以及允许的最大修改次数。

接下来的 $m$ 行，每行包含四个空格分隔的整数。其中第 $i$ 行包含 $u[i]$、$v[i]$、$a[i]$ 和 $b[i]$，表示初始时，在蘑菇 $u[i]$ 旁指向蘑菇 $v[i]$ 的指示牌上写有从 $a[i]$ 到 $b[i]$ 的第 $i$ 个连续数字区间。

输出格式

程序必须输出到标准输出。

输出一个整数，表示在自由进行最多 $k$ 次修改后，可能达到的最大效用值。

数据范围

对于所有测试数据，输入满足以下范围：

• $2 \le n \le 150\,000$
• $1 \le m \le 300\,000$
• $0 \le k \le 10^{12}$
• 对于所有 $1 \le i \le m$，有 $1 \le u[i], v[i] \le n$ 且 $u[i] \neq 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 \neq j$ 且 $u[i] = u[j]$，则 $b[i] < a[j]$ 或 $b[j] < a[i]$

子任务

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

样例

输入样例 1

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

输出样例 1

8

说明 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。

输入样例 2

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

输出样例 2

10

说明 2

指示牌初始时与样例 1 相同。我们可以进行 $k = 1$ 次修改。

一种最优方案是在蘑菇 5 旁指向蘑菇 6 的指示牌上添加数字 2。除了样例 1 中的 8 个有序对 $(s, d)$ 之外，我们还得到了 $(4, 2)$ 和 $(5, 2)$。效用值为 10。

输入样例 3

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

输出样例 3

13

说明 3

指示牌初始时与样例 1 相同。我们可以进行 $k = 2$ 次修改。

一种最优方案是从蘑菇 6 旁指向蘑菇 1 的指示牌上删除数字 3，并在蘑菇 6 旁指向蘑菇 3 的指示牌上添加数字 3。这使得蜗牛可以从任意蘑菇出发，通过遵循指示牌移动到蘑菇 3。效用值为 13。