#P18722. Two Histograms

    ID: 18058 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-线性 DP状态维度消除二分查找增量维护

Two Histograms

Two Histograms

有三个大小均为 106×10610^6\times10^6 的方格图。每个格子有整数坐标 (x,y)(x,y):xx 从左到右编号为 11 至 10610^6,yy 从下到上编号为 11 至 10610^6。每个格子要涂成黑色或白色。

第一幅图的黑色部分必须构成从底部向上生长的直方图:若一个格子是黑色,则同一列中它下面的所有格子也必须是黑色。每列的黑色高度可以独立选择。

第二幅图的黑色部分必须构成从左向右生长的直方图:若一个格子是黑色,则同一行中它左面的所有格子也必须是黑色。每行的黑色宽度可以独立选择。

第三幅图由前两幅图确定:格子 (x,y)(x,y) 当且仅当在前两幅图中都为黑色时才为黑色;否则为白色。第三幅图是最终画作。

原题中两幅直方图及其交集示意图

上图来自原题,依次展示第一幅、第二幅和最终画作。

共有 nn 位评委。所有评委使用的区域都是宽为 kk、高为 11 的矩形。第 ii 位评委的区域包含格子

(xi,yi),(xi+1,yi),…,(xi+k−1,yi).(x_i,y_i),(x_i+1,y_i),\ldots,(x_i+k-1,y_i).

这 nn 个矩形区域互不重叠。

第 ii 位评委只比较该矩形最左端格子 (xi,yi)(x_i,y_i) 和最右端格子 (xi+k−1,yi)(x_i+k-1,y_i) 的颜色。如果两端同色,则拒绝这幅画作;如果两端异色,则认可它,并按照最左端的颜色给分:最左端为白色时给 aia_i 分,为黑色时给 bib_i 分。

画作必须获得所有评委认可。请在所有能获得全体评委认可的画作中,求总得分的最大值。总得分等于所有评委给分之和。

输入格式

第一行包含两个整数 n,kn,k(1≤n≤3⋅1051\le n\le3\cdot10^5,2≤k≤1062\le k\le10^6)。

接下来 nn 行,每行包含四个整数 xi,yi,ai,bix_i,y_i,a_i,b_i:

1≤xi≤106−k+1,1≤yi≤106,1\le x_i\le10^6-k+1,\qquad1\le y_i\le10^6, 1≤ai,bi≤109.1\le a_i,b_i\le10^9.

保证给出的 nn 个矩形区域互不重叠。输入只有一组数据。

输出格式

如果不存在能获得全体评委认可的画作,输出 −1-1;否则输出最大总得分。

原样例

样例 1:

5 2
1 1 1 2
3 1 1 10
5 1 5 6
2 2 3 2
4 2 5 9
26

样例 2:

6 3
1 1 2 4
5 1 4 9
2 3 7 4
5 3 3 1
1 5 5 7
4 5 6 4
36

样例 3:

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

样例 4:

10 3
4 2 5 2
10 2 8 10
1 2 1 4
12 1 8 6
6 3 7 10
8 1 1 9
11 3 5 5
7 2 10 5
3 3 6 4
4 1 9 4
72