CF434D Nanami's Power Plant

七海喜欢玩游戏，并且非常擅长。这一天她正在玩一个新游戏，内容是操作发电厂。七海的任务是控制发电厂中的发电机，以产出最大的总输出。 发电厂有 $n$ 台发电机。每台发电机都需要设定一个发电等级。发电等级是一个整数（可能为零或负数），第 $i$ 台发电机的发电等级必须在 $l_{i}$ 到 $r_{i}$ 之间（包含端点）。每台发电机的输出由一个特定的二次函数 $f(x)$ 计算，其中 $x$ 是该台发电机的发电等级。每台发电机有自己独立的函数，第 $i$ 台发电机对应的函数为 $f_{i}(x)$。 除此之外，还有 $m$ 条发电机之间的其他约束。设第 $i$ 台发电机的发电等级为 $x_{i}$。每一个约束有如下形式：$x_{u} \leq x_{v} + d$，其中 $u$ 和 $v$ 是两台不同发电机的编号，$d$ 是一个整数。 七海觉得游戏太繁琐，但她秉性不容许轻言放弃。所以，她决定让程序帮她计算答案（即所有发电机的最大总输出）。结果，这成了你的任务。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 50; 0 \leq m \leq 100$），表示发电机的数量和约束的数量。 接下来的 $n$ 行，每行包含三个整数 $a_{i},\ b_{i},\ c_{i}$（$|a_{i}| \leq 10; |b_{i}|, |c_{i}| \leq 1000$），表示函数 $f_{i}(x) = a_{i} x^{2} + b_{i} x + c_{i}$ 的系数。 再接下来的 $n$ 行，每行包含两个整数 $l_{i},\ r_{i}$（$-100 \leq l_{i} \leq r_{i} \leq 100$），分别表示第 $i$ 台发电机的发电等级下限和上限。 接下来 $m$ 行，每行包含三个整数 $u_{i},\ v_{i},\ d_{i}$（$1 \leq u_{i}, v_{i} \leq n; u_{i} \neq v_{i}; |d_{i}| \leq 200$），表示一条约束：$x_{u_{i}} \leq x_{v_{i}} + d_{i}$。

输出一行一个整数，表示所有发电机能够达到的最大总输出值。保证至少存在一种合法配置。

在第一个样例中，$f_{1}(x) = x$，$f_{2}(x) = x + 1$，$f_{3}(x) = x + 2$，所以我们要最大化发电等级之和。约束为 $x_{1} \leq x_{2}$，$x_{2} \leq x_{3}$，$x_{3} \leq x_{1}$，因此 $x_{1} = x_{2} = x_{3}$。最优解是 $x_{1} = x_{2} = x_{3} = 2$，总输出为 $9$。 在第二个样例中，约束为 $|x_{i} - x_{i+1}| \leq 3$，其中 $1 \leq i < n$。最优的一个方案为 $x_{1} = 1$，$x_{2} = 4$，$x_{3} = 5$，$x_{4} = 8$，$x_{5} = 7$。 由 ChatGPT 5 翻译