Description

安徽芜湖有\(n\)个机场，一共有\(m\)条线路在空管部门报备。
每条线路单向连接两个机场，并且需要的通行时间每天都可能不一样。
具体来说，设目前是第\(x\)天，那么第\(i\)条线路所需要的通行时间为\(k_ix+b_i\)。
一年一共有\(H\)天，也就是说，\(x\)取\([0,H]\)中的整数。
现在大司马想从\(1\)号机场在一天内换乘任意多次航班前往\(n\)号机场，他总是选择用时最短的方式，现在他想知道哪一天需要花最长的时间。

Format

Input

每个测试点仅包含一组输入数据。
第一行三个整数\(n,m,H(1 \leq n,m \leq 114514,1 \leq H \leq 10^9)\)，表示机场的数量，线路的数量和\(x\)的取值范围。
接下来\(m\)行，每行四个整数\(u_i,v_i,k_i,b_i(1 \leq u_i,v_i \leq n,-10^9 \leq k_i,b_i \leq 10^9)\)，表示一条线路从\(u_i\)机场单向前往\(v_i\)机场，并且第\(x\)天需要\(k_ix+b_i\)的时间来通行。
同一对机场之间可能有多条航线，一条航线的起点和终点可能相同。
保证在\([0,H]\)中的任意一天，每条航线的长度非负且不超过\(10^9\)，且从\(1\)号机场可以到达\(n\)号机场。

Output

输出一行一个整数，表示最长的用时。

Sample 1

Input

4 6 2
1 2 -2 6
1 3 3 3
1 4 -1 4
3 2 1 5
3 4 -3 7
2 4 0 5

Output

4

Limitation

2s, 512MB for each test case.

Source

vbs