Economical Flight Route Planning

In this problem, Shinben Airlines plans a flight from location A to location B. The ground is a perfect plane at height 0, and there are N navigation points (numbered from 0 to N-1) with M bidirectional air routes connecting them. Navigation point 0 is the departure point A and navigation point N-1 is destination B.

Each air route connects two navigation points and is associated with two integer parameters \(H\) and \(W\). When using an air route at a chosen flight altitude \(h\) (which you can decide on at the departure point of that route), the cost incurred for that route is \[ (H - h)^2 + W, \] where any difference is squared.

At every navigation point, you may adjust your current altitude. Increasing (climbing) your altitude by 1 unit costs \(C\), while decreasing (descending) is free. Note that you begin at altitude 0 at point A. Your task is to plan a route from point 0 to point N-1 with minimum total cost, where the total cost includes both the flight costs on the routes and any climbing costs incurred at the navigation points.

Input Format: The first line contains three integers \(N\), \(M\) and \(C\) representing the number of navigation points, the number of air routes, and the climbing cost per height unit respectively. Each of the next \(M\) lines contains four integers \(u\), \(v\), \(H\), and \(W\) meaning that there is a bidirectional air route between points \(u\) and \(v\) with parameters \(H\) and \(W\).

Output Format: Output a single integer representing the minimum cost required to travel from point A (node 0) to point B (node N-1). If it is impossible to reach the destination, output -1.

Note: On each route the chosen flight altitude \(h\) can be any integer between 0 and \(H_{max}\) (where \(H_{max}\) is the maximum \(H\) among all routes). It is always optimal to choose a flight altitude \(h\) that does not exceed the route's parameter \(H\) because choosing a higher altitude would unnecessarily increase \((H-h)^2\).

inputFormat

The first line of input contains three integers: \(N\) \(M\) \(C\). \(N\) is the number of navigation points (numbered from 0 to N-1), \(M\) is the number of air routes, and \(C\) is the climbing cost per unit of altitude.

Each of the following \(M\) lines contains four integers \(u\), \(v\), \(H\), \(W\), meaning that there is a bidirectional route between nodes \(u\) and \(v\) with parameters \(H\) and \(W\).

outputFormat

Output a single integer: the minimum total cost to travel from node 0 (point A) to node N-1 (point B).

sample

3 2 1
0 1 5 10
1 2 5 10

25