#2695. 飞行计划

内存限制:128 MiB 时间限制:10 Sec

题目描述

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*10^5;输入保证答案不超出32位有符号整型。