#P17872. [Ontak2019]WAT

[Ontak2019]WAT

— 漏斗浇花

花园有 m+2m+2 行、nn 列。行编号为 0,1,…,m+10,1,\ldots,m+1,列编号为 1,2,…,n1,2,\ldots,n。雨水可能从第 00 行的任意一列出现,通常沿所在列向下流动,直到底部第 m+1m+1 行。

你有 mm 个可选漏斗。第 ii 个漏斗安装在第 ii 行,覆盖第 ℓi\ell_i 至第 rir_i 列,出水口在第 hih_i 列,重量为 wiw_i。若安装这个漏斗,进入这一行且列坐标位于 [ℓi,ri][\ell_i,r_i] 的水滴都会被引到下一行的第 hih_i 列;其他列的水滴保持原列坐标。不安装时,这一行的水滴全部竖直下落。

选择一些漏斗,使从任意起始列落下的水最终都到达底部同一个格子。求所选漏斗的最小总重量。

输入格式

第一行两个整数 m,nm,n。

接下来 mm 行,第 ii 行四个整数 ℓi,ri,hi,wi\ell_i,r_i,h_i,w_i,描述第 ii 个漏斗。顺序就是从上到下的行顺序。

输出格式

输出一个整数,表示最小总重量。若无法将所有水汇集到一个格子,输出 -1。

数据范围及原文说明

1≤m≤5000001\le m\le500000,1≤n≤1091\le n\le10^9,1≤ℓi≤hi≤ri≤n1\le\ell_i\le h_i\le r_i\le n。

原 PDF 将最后一个不等号印为 ri<nr_i<n,但样例明确含 ri=nr_i=n,这里按允许覆盖最右列理解。原 PDF 未给出重量 wiw_i 的数值上限;重量按非负量理解,标程使用 64 位整数存储费用。未凭空补写原题没有的上限。

子任务 漏斗数上限 分值
1 24 9
2 500 15
3 1500 14
4 10000 18
5 100000 37
6 500000 7

样例 1

输入:

5 6
2 4 3 3
1 2 2 5
3 6 5 4
4 6 4 9
2 4 3 2

输出:

16

样例 2

输入:

3 5
2 4 3 7
1 3 1 2
2 5 4 3

输出:

-1