题目背景

天界区域的大陆上共有 $n$ 个国家，$m$ 条航线。第 $i$ 条航线的飞机在时刻 $s_i$ 从国家 $u_i$ 起飞，在时刻 $t_i$ 降落到国家 $v_i$。

你现在在国家 $1$ 的机场，初始的时刻是 $0$，希望搭乘飞机到达国家 $n$。因为你没有除了国家 $n$ 以外任何国家的签证，所以你在到达国家 $n$ 之前，都不能离开机场。只能在机场内等待转机。

天界大陆规定：如果你在一个机场连续停留了 $t$ 秒，就要向百合咲大人上交 $t^2$ 枚风云币的机场建设税。由于你购买了百合咲ミカ联名随心飞，所以所有机票都是免费的。你的目标是尽可能地少交税。

求出你总共最少要交多少风云币作为机场建设税。

如果你不能从 $1$ 号国家到达 $n$ 号国家，那么输出 -1。

输入格式

第一行有两个整数，表示国家数量 $n$ 和航线数量 $m$。
接下来 $m$ 行，每行四个整数 $u_i, v_i, s_i, t_i$，描述一条航线。

输出格式

输出一行一个整数表示答案。

如果你不能从 $1$ 号国家到达 $n$ 号国家，那么输出 -1。

样例

样例输入 1

4 5
3 3 70 100
1 3 40 50
2 4 300 420
1 2 20 21
3 4 110 1337

样例输出 1

2100

样例输入输出 2

见选手目录下的 tax/tax2.in 和 tax/tax2.ans。

这个样例满足测试点 $3 \sim 5$ 的约定。

样例输入输出 3

见选手目录下的 tax/tax3.in 和 tax/tax3.ans。

这个样例满足测试点 $6 \sim 7$ 的约定。

样例输入输出 4

见选手目录下的 tax/tax4.in 和 tax/tax4.ans。

这个样例满足测试点 $8 \sim 10$ 的约定。

样例输入输出 5

见选手目录下的 tax/tax5.in 和 tax/tax5.ans。

这个样例满足测试点 $11 \sim 14$ 的约定。

样例输入输出 6

见选手目录下的 tax/tax6.in 和 tax/tax6.ans。

这个样例满足测试点 $15 \sim 19$ 的约定。

数据规模与约定

本题共 $25$ 个测试点，每个测试点 $4$ 分。

测试点编号	$n$	$m$	特殊约定
$1,2$	$\leq 10$		无
$3,4,5$	$\leq 50$	$\leq 100$	$t_i \leq 2000$
$6,7$	$=3$	$\leq 2 \times 10^5$	$u_i = v_i - 1$
$8,9,10$	$=4$
$11 \sim 14$	$\leq 5000$		无
$15 \sim 19$	$\leq 2 \times 10^5$		每个国家起降的航线总数均不超过 $10$
$20 \sim 25$			无

对全部的测试数据，保证 $1 \leq n, m \leq 2 \times 10^5$，$1 \leq u_i, v_i \leq n$，$1 \leq s_i < t_i \leq 10^9$，且所有的 $s _ i, t _ i$ 都互不相同。