Description

Shenben Airlines has a flight from $A$ to $B$ and needs to plan the most economical route. To simplify, we assume the ground is a plane at height $0$, with $N$ waypoints and $M$ bidirectional airways. Each airway connects two waypoints and has two parameters $H$ and $W$, meaning that traversing this airway at altitude $h$ costs $(H - h)^2 + W$. At each waypoint you may climb or descend; each unit of climb costs $C$, while descending is free. Waypoint $0$ is $A$, and waypoint $N - 1$ is $B$.

Input Format

The first line contains 3 positive integers $N$, $M$, and $C$, as described above. The next $M$ lines each contain 4 integers $u, v, H, W$, indicating there is an airway between $u$ and $v$ with parameters $H$ and $W$.

Output Format

Output a single line with one integer, the minimum cost from $A$ to $B$.

3 2 5
0 1 10 10
1 2 20 10

114

Hint

Constraints:

• For 10% of the testdata: $N, M \le 5$, $H \le 200$.
• Additionally, for 20% of the testdata: $N \le 100$, $M \le 500$, $H \le 100$.
• For all testdata: $N \le 2000$, $M \le 10000$, $C \le 10$, $0 \le u, v < N$, $0 \le H \le 10^5$, $0 \le W \le 2 \times 10^5$. The input guarantees the answer does not exceed a 32-bit signed integer.

Translated by ChatGPT 5