题目背景

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<=5$，$H<=200$；

另有20%的数据，$N<=100$，$M<=500$，$H<=100$；

对于全部的测试数据，$N<=2000$，$M<=10000$，$C<=10$，$0<=u,v<N$，$0<=H<=10^5$，$0<=W<=2\times 10^5$；输入保证答案不超出32位有符号整型。