题目描述

Byteotia 有 $n$ 座城市，编号为 $1,2,\ldots,n$。任意两座城市之间都有一条直接道路，因此每座城市都有 $n-1$ 条出城道路。道路彼此之间不会相交，也不能从一条道路中途转到另一条道路。

每条出城道路的起点处都有一块路标。因此总共有 $n(n-1)$ 块路标。

由于负责路标的机构预算不足，路标上的内容十分混乱。所有路标上一共给出了若干个整数区间；一块路标可能包含一个或多个区间，也可能为空。

路标内容保证满足以下规则：

1. 位于城市 $u$、指向城市 $v$ 的道路旁的路标不能包含数字 $u$，但可以包含也可以不包含数字 $v$；
2. 同一座城市中的任意两块不同路标不能同时包含同一个数字。

当一个居民位于城市 $x$，想去城市 $y$ 时，他会执行以下过程：

• 在城市 $x$ 的所有路标中寻找包含数字 $y$ 的那一块；
• 如果找到，则沿这块路标对应的道路前往下一座城市；
• 到达后重复上述过程，直到抵达 $y$。

由于第二条规则，同一座城市至多有一块路标包含目标城市编号 $y$。

旅途中可能出现以下情况：

• 找不到包含 $y$ 的路标，于是旅行失败；
• 陷入无限循环，永远无法到达 $y$。

如果从 $x$ 出发、以 $y$ 为目标时最终一定能够按照上述规则到达 $y$，则称有序城市对 $(x,y)$ 是一个好城市对。

显然 $(x,x)$ 也是好城市对。

你正在审计负责路标的机构，可以对所有路标进行恰好 $k$ 次修改。一次修改可以是：

• 在某块路标上添加一个城市编号；或
• 从某块路标上删除一个城市编号。

修改后，一块路标上的数字不再要求能表示为连续区间，但仍必须满足最开始的两条规则。

请进行最多 $k$ 次修改，使好城市对的数量尽可能大，并输出这个最大值。

输入格式

第一行包含三个整数 $n,m,k$：

• $2\le n\le150000$；
• $1\le m\le300000$；
• $0\le k\le10^{12}$。

接下来 $m$ 行，每行包含四个整数 $u_i,v_i,a_i,b_i$：

• $1\le u_i,v_i\le n$，$u_i\ne v_i$；
• $1\le a_i\le b_i\le n$；
• 表示在城市 $u_i$、通往城市 $v_i$ 的道路旁的路标上，写有区间 $[a_i,b_i]$ 中的所有城市编号。

同一块路标可以由多行区间共同描述。所有给出的路标内容保证满足题目开头的两条规则。

输出格式

输出一个整数，表示进行 $k$ 次修改后，能够得到的最大好城市对数量。

样例 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

8

此时好城市对为

$(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(1,2),(6,2)$。

例如从城市 $6$ 前往城市 $2$ 时，先按包含数字 $2$ 的路标走到 $1$，再从 $1$ 走到 $2$。

样例 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

10

可以在城市 $5$ 通往城市 $6$ 的路标上增加数字 $2$，此时 $(4,2)$ 和 $(5,2)$ 也变成好城市对。

样例 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

13

可以从道路 $6\to1$ 的路标中删除数字 $3$，再把数字 $3$ 加到道路 $6\to3$ 的路标中。这样任意城市都能够到达城市 $3$，最终好城市对总数为 $13$。

子任务