说明

Alice 喜欢一款名为弹球（Pinball）的视频游戏。弹球的规则如下。

弹球的棋盘是一个有 $(M + 2)$ 行和 $N$ 列的网格。棋盘的第一行是棋盘的顶部，第 $(M + 2)$ 行是棋盘的底部。位于第 $i$ 行、第 $j$ 列的格子记为 $(i, j)$。

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

一天，Alice 注意到，由于球可能到达底部的任何格子，这使得击球变得困难。Alice 决定在棋盘上适当地放置一些如下所述的装置，使得球可能到达的底部格子有且仅有一个。

共有 $M$ 个装置，编号从 1 到 $M$。每个装置都与棋盘的行平行。装置 $i$（$1 \leq i \leq M$）位于从 $(i + 1, A_i)$ 到 $(i + 1, B_i)$ 的格子上，因此它总共覆盖 $(B_i - A_i + 1)$ 个格子。当一个球到达该装置上的任意格子时，它会被传送到格子 $(i + 1, C_i)$（$A_i \leq C_i \leq B_i$）。之后，被传送的球将沿着第 $C_i$ 列垂直移动。每个装置对同一个球最多作用一次。

在游戏中，放置装置 $i$（$1 \leq i \leq M$）需要支付 $D_i$ 日元。她将从这 $M$ 个装置中选择一部分放置在棋盘上，使得球可能到达的底部格子有且仅有一个。她希望通过高效地放置装置来最小化总成本。

:::align{center}

图示：一个弹球棋盘的例子。这里 $M = 2$，$N = 4$。一个球出现在第一行的格子 $(1, 2)$。然后，球将移动到 $(2, 2)$，并被装置 1 传送到 $(2, 3)$。最终它到达底部的格子 $(4, 3)$。 :::

任务

编写一个程序，根据给定的棋盘大小和装置信息，计算出使得球可能到达的底部格子有且仅有一个所需的最小总成本。

输入格式

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

• 输入的第一行包含两个以空格分隔的整数 $M, N$。这表示棋盘有 $(M + 2)$ 行和 $N$ 列，且装置的数量为 $M$。
• 接下来的 $M$ 行中，第 $i$ 行（$1 \leq i \leq M$）包含四个以空格分隔的整数 $A_i, B_i, C_i, D_i$。这表示装置 $i$ 位于从 $(i + 1, A_i)$ 到 $(i + 1, B_i)$ 的格子上。装置 $i$ 总共覆盖 $(B_i - A_i + 1)$ 个格子。装置 $i$ 会将到达这些格子中任意一个的球传送到格子 $(i + 1, C_i)$。放置装置 $i$ 的成本为 $D_i$ 日元。

输出格式

向标准输出写入一行。输出应包含一个整数，表示使得球可能到达的底部格子有且仅有一个所需放置装置的最小总成本。如果无法通过放置装置满足该条件，则输出 $-1$。

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

25

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

-1

提示

样例 1 解释

棋盘和装置的位置如下图所示。每个装置上方标注的数字表示放置它所需的成本。

:::align{center} :::

如果从五个装置中选择装置 2、4、5 进行放置，棋盘将变为如下图所示。

:::align{center} :::

此时，从第一行任意格子出现的球最终都会到达底部的格子 $(7, 3)$。放置这些装置的总成本为 25 日元。由于无法用低于 25 日元的总成本实现“球可能到达的底部格子有且仅有一个”这一条件，因此你应该输出 25。

样例 2 解释

无法通过放置装置使得球可能到达的底部格子有且仅有一个。

约束条件

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

• $1 \leq M \leq 100\,000$。
• $2 \leq N \leq 1\,000\,000\,000$。
• $1 \leq A_i \leq C_i \leq B_i \leq N$（$1 \leq i \leq M$）。
• $1 \leq D_i \leq 1\,000\,000\,000$（$1 \leq i \leq M$）。

子任务

子任务 1 [11 分]

满足以下条件：

• $M \leq 10$。
• $N \leq 1000$。

子任务 2 [18 分]

满足以下条件：

• $M \leq 200$。

子任务 3 [22 分]

满足以下条件：

• $M \leq 1000$。

子任务 4 [49 分]

• 无额外约束。

翻译由 DeepSeek V3.2 完成