Background

Beyond the limit of supersonic speed, yet not as magnificent and ever-changing as the aurora.

Faint pulses carve out a world that was once pure chaos.

A deep blue flickers slowly, and epic red welcomes the peak.

At the end of the blood-red sunset lie the stars of the coming night.

Even the star-filled midnight sky can be covered by smoke from hell.

The blazing red purgatory fades away; only golden ruins last forever.

What awaits everyone here is a hard yet brilliant journey.

Problem Description

If positive integers $a$ and $b$ satisfy:

• The product of $a$ and $b$ is the $k$-th power of a positive integer, that is, there exists a positive integer $c$ such that $ab=c^k$.

Then we call $(a,b)$ a pair of perfect numbers.

There is a directed acyclic graph with $n$ nodes and $m$ edges. Each edge in this graph has two attributes: a weight and a length.

If a path $P$ satisfies one of the following conditions, then it is called a perfect path:

• $P$ contains only one edge.

• Starting from its beginning, $P$ consists of $p\ (p\ge 2)$ edges $e_1, e_2, e_3, \ldots e_p$. For any $1\leq i\leq p-1$, the weights of $e_i$ and $e_{i+1}$ form a perfect-number pair.

You need to find the length of the longest perfect path in the graph. The length of a path is defined as the sum of the lengths of all edges on the path.

Input Format

The first line contains three integers $n,m,k$, representing the number of nodes, the number of edges, and the parameter of perfect-number pairs.

The next $m$ lines each contain four integers $u,v,w,l$, meaning there is a directed edge from $u$ to $v$ with weight $w$ and length $l$.

Output Format

The first line contains one integer $ans$, representing the length of the longest perfect path.

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

Hint

【Help and Hints】

To make it easier for contestants to test their code, this problem additionally provides two extra sample tests.

Sample Input 1 Sample Output 1

Sample Input 2 Sample Output 2

【Sample Explanation】

The directed acyclic graph in the sample is shown in the figure, where the red numbers on edges are the weights, and the black numbers are the lengths:

The longest perfect path is $2\to 5\to 3$, because the weights $2$ and $18$ of these two edges satisfy $2\times 18=6^2$, which is a perfect-number pair. The path length is $5+9=14$.

In addition, $2\to 1\to 4\to 3,\ \ 2\to 4\to 3,\ \ 1\to 5\to 3$ and so on are also perfect paths, but they are not the longest.

In the graph, the path $2\to 1\to 5\to 3$ has length $15$, which is longer, but it is not a perfect path, because the product of the first two edge weights $24$ and $8$ is $192$, which is not a square of a positive integer. That is, $(24,8)$ is not a perfect-number pair.

【Constraints】

This problem uses bundled tests.

For $100\%$ of the testdata: $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$.

The given graph is not guaranteed to be weakly connected. There may be multiple edges from one node to another, but it is guaranteed that the given graph is a directed acyclic graph.

Translated by ChatGPT 5