#P18722. Two Histograms
Two Histograms
Two Histograms
有三个大小均为 的方格图。每个格子有整数坐标 : 从左到右编号为 至 , 从下到上编号为 至 。每个格子要涂成黑色或白色。
第一幅图的黑色部分必须构成从底部向上生长的直方图:若一个格子是黑色,则同一列中它下面的所有格子也必须是黑色。每列的黑色高度可以独立选择。
第二幅图的黑色部分必须构成从左向右生长的直方图:若一个格子是黑色,则同一行中它左面的所有格子也必须是黑色。每行的黑色宽度可以独立选择。
第三幅图由前两幅图确定:格子 当且仅当在前两幅图中都为黑色时才为黑色;否则为白色。第三幅图是最终画作。

上图来自原题,依次展示第一幅、第二幅和最终画作。
共有 位评委。所有评委使用的区域都是宽为 、高为 的矩形。第 位评委的区域包含格子
这 个矩形区域互不重叠。
第 位评委只比较该矩形最左端格子 和最右端格子 的颜色。如果两端同色,则拒绝这幅画作;如果两端异色,则认可它,并按照最左端的颜色给分:最左端为白色时给 分,为黑色时给 分。
画作必须获得所有评委认可。请在所有能获得全体评委认可的画作中,求总得分的最大值。总得分等于所有评委给分之和。
输入格式
第一行包含两个整数 (,)。
接下来 行,每行包含四个整数 :
保证给出的 个矩形区域互不重叠。输入只有一组数据。
输出格式
如果不存在能获得全体评委认可的画作,输出 ;否则输出最大总得分。
原样例
样例 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