题目名称是吸引你点进来的。

从前有个 $n$ 个方格排成一行，从左至右依此编号为 $1, 2, \cdots, n$。

有一天思考熊想给这 $n$ 个方格染上黑白两色。

第 $i$ 个方格上有 $6$ 个属性：$a_i, b_i, w_i, l_i, r_i, p_i$。

如果方格 $i$ 染成黑色就会获得 $b_i$ 的好看度。

如果方格 $i$ 染成白色就会获得 $w_i$ 的好看度。

但是太多了黑色就不好看了。如果方格 $i$ 是黑色，并且存在一个 $j$ 使得 $1 \leq j < i$ 且 $l_i \leq a_j \leq r_i$ 且方格 $j$ 为白色，那么方格 $i$ 就被称为奇怪的方格。

如果方格 $i$ 是奇怪的方格，就会使总好看度减少 $p_i$。

也就是说对于一个染色方案，好看度为： \begin{equation} \sum_{\text{方格}i\text{为黑色}}{b_i} + \sum_{\text{方格}i\text{为白色}}{w_i} - \sum_{\text{方格}i\text{为奇怪的方格}}{p_i} \end{equation}

现在给你 $n, a, b, w, l, r, p$，问所有染色方案中最大的好看度是多少。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行中第 $i$ 行有用空格隔开的 $6$ 个非负整数依次表示 $a_i, b_i, w_i, l_i, r_i, p_i$。

保证 $l_i \leq r_i$。

输出格式

一个非负整数表示所有染色方案中最大的好看度。

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

55

最优染色方案为：白 黑 白 黑 白 黑 白 白 白 白

可以发现只有方格 $6$ 为奇怪的方格。

所以好看度为： \begin{eqnarray} & & w_1 + b_2 + w_3 + b_4 + w_5 + b_6 + w_7 + w_8 + w_9 + w_{10} - p_6 \\ & = & 7 + 4 + 4 + 9 + 5 + 6 + 6 + 5 + 3 + 7 - 1 \\ & = & 55 \end{eqnarray}

限制与约定

设 $a_{\max}$ 为 $a, l, r$ 中的最大值，$v_{\max}$ 为 $b, w$ 中的最大值, $p_{\max}$ 为 $p$ 中的最大值。

时间限制：$2\texttt{s}$

空间限制：$48\texttt{MB}$

来源

VFleaKing

下载

样例数据下载