题目背景

超越音速的极限，不及瑰丽多变的极光；

微弱的脉冲，开拓原本一片混沌的天地；

沉郁的蓝缓缓闪动，史诗的红迎接巅峰；

血色的夕阳尽头，是将夜的星辰；

夜半的满天星空，也会被来自地狱的硝烟掩盖；

炽红炼狱消逝，只金色遗迹永存。

在这里等待着每一位的，都是一段艰苦而璀璨的旅程。

题目描述

若正整数 $a$ 与 $b$ 满足：

• $a$ 与 $b$ 的积是一个正整数的 $k$ 次方，即存在正整数 $c$ 使得 $ab=c^k$。

那么我们称 $(a,b)$ 为一组完美数对。

---

有一个包含 $n$ 个结点和 $m$ 条边的有向无环图，这张图中的每条边都有权值和长度两个属性。

如果一条路径 $P$ 满足以下条件之一，则称其为一条完美路径：

• $P$ 中仅包含一条边。

• $P$ 从其起点开始依次为 $e_1, e_2, e_3, \ldots e_p$ 这 $p\ (p\ge 2)$ 条边，对于任意的 $1\leq i\leq p-1$，$e_i$ 的权值和 $e_{i+1}$ 的权值组成完美数对。

你需要求出图中最长完美路径的长度，一条路径的长度定义为这条路径上所有边的长度之和。

输入格式

第一行：三个整数 $n,m,k$，分别表示有向无环图的结点数、边数和完美数对的参数。

接下来 $m$ 行：每行四个整数 $u,v,w,l$，表示有一条权值为 $w$，长度为 $l$ 的有向边从 $u$ 连向 $v$。

输出格式

第一行：一个整数 $ans$，表示最长完美路径的长度。

5 7 2
2 5 2 5
5 3 18 9
2 4 6 7
4 3 6 3
2 1 24 2
1 4 6 8
1 5 8 4

14

提示

【帮助与提示】

为方便选手测试代码，本题额外提供两组附加样例供选手使用。

样例输入1 样例输出1

样例输入2 样例输出2

---

【样例解释】

样例中给出的有向无环图如图所示，其中边上的红色数字为边的权值，黑色数字为边的长度：

最长完美路径为 $2\to 5\to 3$，因为这两条边的权值 $2$ 和 $18$ 满足 $2\times 18=6^2$，是完美数对，此路径长度为 $5+9=14$。

此外，$2\to 1\to 4\to 3,\ \ 2\to 4\to 3,\ \ 1\to 5\to 3$ 等也是完美路径，但不是最长的。

图中，$2\to 1\to 5\to 3$ 长度为 $15$，是一条更长的路径，但它并不是完美路径，因为前两个边权 $24$ 和 $8$ 的乘积为 $192$，不是正整数的平方，即 $(24,8)$ 不是完美数对。

---

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据：$1\leq n\leq 10^5,\ \ 1\leq m\leq 2\times 10^5,\ \ 1\leq k\leq 10,\ \ 1\leq u,v\leq n,\ \ 1\leq w\leq 10^5,\ \ 1\leq l\leq 10^4$。

给出的图不保证弱连通，图中从一个点到另一个点可能存在多条边，但保证给出的图是有向无环图。

子任务编号	$n\leq$	$m\leq$	$w\leq$	$k\leq$	特殊性质	分值
Subtask 1	$10^5$	$2\times 10^5$	$10^5$	$1$	无	$18$
Subtask 2	$10$		$100$	$2$		$12$
Subtask 3	$600$	$1.5\times 10^3$	$10^3$			$10$
Subtask 4	$10^5$	$2\times 10^5$	$10^5$		$w$ 为素数	$15$
Subtask 5					无
Subtask 6	$600$	$1.5\times 10^3$	$10^3$	$5$		$10$
Subtask 7	$10^5$	$2\times 10^5$	$10^5$	$10$		$20$