背景

1. wqs喜欢模拟飞行。

2. clj开了一家神犇航空，由于clj还要玩游戏，所以公司的事务由你来打理。

注意：题目中只是用了这样一个背景，并不与真实/模拟飞行相符

题目描述

神犇航空有一架航班从 $A$ 地飞往 $B$ 地，需要规划一条最经济的飞行线路。为了简化问题，我们认为地面是一个平面，高度为 $0$，上有 $N$ 个航路点，有 $M$ 条双向航线，每条航线连接两个航路点，有两个参数 $H$ 和 $W$，表示以$h$高度通过这条航路，费用为 $(H-h)^2+W$。在每个航路点可以爬升/下降高度，每爬升一个高度需要费用 $C$，而下降不需要费用。航路点 $0$ 为 $A$ 地，$N-1$ 为 $B$ 地。

输入格式

第一行 $3$ 个正整数，$N$，$M$ 和 $C$，含义如题目所述；

以下 $M$ 行，每行 $4$ 个整数，$u,v,H,W$，表示 $u,v$ 之间有一条航线，$H,W$ 为描述中的两个参数。

输出格式

仅一行，一个整数，表示 $A$ 地到 $B$ 地的最小费用。

3 2 5
0 1 10 10
1 2 20 10

114

提示

对于 $10\%$ 的数据，$N,M \le 5$，$H \le 200$；

另有 $20\%$ 的数据，$N \le 100$，$M \le 500$，$H\le 100$；

对于全部的测试数据，$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$；输入保证答案不超出 $32$ 位有符号整型。