Alice 喜欢玩一款名为“弹珠台”（Pinball）的电子游戏。弹珠台的游戏规则如下：

弹珠台的棋盘是一个 $(M + 2)$ 行 $N$ 列的方格网。棋盘的第一行是顶部，第 $(M + 2)$ 行是底部。第 $i$ 行第 $j$ 列的方格记作 $(i, j)$。

一个小球会出现在第一行的某个方格中，并垂直向下落向棋盘底部。也就是说，如果一个小球出现在方格 $(1, i)$ ($1 \le i \le N$)，它将穿过 $(j, i)$ ($2 \le j \le M + 1$)，并最终到达底部的 $(M + 2, i)$。当 Alice 成功击回小球时，她会获得分数。

有一天，Alice 发现很难击回小球，因为小球可能会到达底部的任何一个方格。Alice 决定在棋盘上适当地放置一些装置，使得小球最终只能到达底部的一个特定方格。

棋盘上共有 $M$ 个编号为 $1$ 到 $M$ 的装置。每个装置都与棋盘的行平行。第 $i$ 个装置 ($1 \le i \le M$) 位于第 $(i + 1)$ 行，覆盖了从 $(i + 1, A_i)$ 到 $(i + 1, B_i)$ 的方格。因此，它总共覆盖了 $(B_i - A_i + 1)$ 个方格。当小球到达该装置覆盖的任意方格时，它会被转移到方格 $(i + 1, C_i)$ ($A_i \le C_i \le B_i$)。此后，被转移的小球将沿第 $C_i$ 列垂直向下移动。每个装置与一个小球的交互不会超过一次。

她需要支付 $D_i$ 日元来在棋盘上放置第 $i$ 个装置 ($1 \le i \le M$)。她将选择 $M$ 个装置中的一部分放置在棋盘上，使得小球最终只能到达底部的一个方格。她希望通过高效地放置装置来最小化总成本。

图：弹珠台棋盘示例。$M = 2, N = 4$。一个小球出现在第一行的方格 $(1, 2)$。然后，小球移动到 $(2, 2)$，并被装置 1 转移到 $(2, 3)$。它最终到达底部的方格 $(4, 3)$。

输入格式

从标准输入读取以下数据：

• 第一行包含两个空格分隔的整数 $M, N$。这意味着棋盘有 $(M + 2)$ 行和 $N$ 列，装置数量为 $M$。
• 接下来的 $M$ 行中，第 $i$ 行 ($1 \le i \le M$) 包含四个空格分隔的整数 $A_i, B_i, C_i, D_i$。这意味着第 $i$ 个装置位于第 $(i + 1)$ 行，覆盖了从 $(i + 1, A_i)$ 到 $(i + 1, B_i)$ 的方格。第 $i$ 个装置将到达这些方格之一的小球转移到 $(i + 1, C_i)$。放置第 $i$ 个装置的成本为 $D_i$ 日元。

输出格式

输出一行到标准输出。该输出应包含一个整数，表示为了使小球最终只能到达底部的一个方格，放置装置所需的最少总成本。如果无法通过放置装置满足这些条件，则输出 -1。

数据范围

所有输入数据满足以下条件：

• $1 \le M \le 100\,000$。
• $2 \le N \le 1\,000\,000\,000$。
• $1 \le A_i \le C_i \le B_i \le N$ ($1 \le i \le M$)。
• $1 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le M$)。

子任务

子任务 1 [11 分]

满足以下条件： $M \le 10$。 $N \le 1\,000$。

子任务 2 [18 分]

满足以下条件： * $M \le 200$。

子任务 3 [22 分]

满足以下条件： * $M \le 1\,000$。

子任务 4 [49 分]

无附加限制。

样例

样例输入 1

5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10

样例输出 1

25

样例输入 2

3 5
2 4 3 10
1 3 1 20
2 5 4 30

样例输出 2

-1

说明

在样例 1 中，如果放置五个装置中的 2, 4, 5 号装置，棋盘状态如下图所示。此时，出现在第一行任意方格的小球最终都会到达底部的方格 $(7, 3)$。放置这些装置的总成本为 25 日元。由于无法以低于 25 日元的成本使小球最终只能到达底部的一个方格，因此输出 25。

在样例 2 中，无法通过放置装置使得小球最终只能到达底部的一个方格，因此输出 -1。