← 返回题目列表

Codeforces · 434/D

D. 七海的发电厂

中文机器翻译题面 查看原题

七海喜欢玩游戏,而且也很擅长。这天她正在玩一个新游戏,其中涉及经营一座发电厂。七海的工作是控制工厂里的发电机并产生最大的输出。

工厂中有 n 台发电机。每个发电机应设置为发电水平。生成级别是一个整数(可能为零或负数),第 i 个生成器的生成级别应在 li 和 ri 之间(两者均包含在内)。发电机的输出可以使用某个二次函数 f(x) 来计算,其中 x 是发电机的发电水平。每个生成器都有自己的函数,第 i 个生成器的函数表示为 fi(x)。

然而,发电机还有 m 进一步的限制。设第i个发电机的发电水平为xi。每个限制的形式为 xu ≤ xv + d,其中 u 和 v 是两个不同生成器的 ID,d 是整数。

七海觉得这个游戏很乏味,但放弃违背了她的信条。所以她决定编写一个程序来计算她的答案(发电机的最大总输出)。不知何故,这成了你的工作。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 50; 0 ≤ m ≤ 100) — 生成器的数量和限制的数量。

接下来是 n 行,每行包含三个整数 ai、bi 和 ci (|ai| ≤ 10; |bi|, |ci| ≤ 1000) — 函数 fi(x) 的系数。即 fi(x) = aix2 + bix + ci。

接下来是n行,每行包含两个整数li和ri (- 100 ≤ li ≤ ri ≤ 100)。

接下来是 m 行,每行包含三个整数 ui、vi 和 di (1 ≤ ui, vi ≤ n; ui ≠ vi; |di| ≤ 200),描述一个限制。第 i 个限制是 xui ≤ xvi + di。

输出

打印一行包含单个整数 - 所有生成器的最大输出。保证至少存在一种有效的配置。

示例

输入 #1

3 3
0 1 0
0 1 1
0 1 2
0 3
1 2
-100 100
1 2 0
2 3 0
3 1 0

输出 #1

9

输入 #2

5 8
1 -8 20
2 -4 0
-1 10 -10
0 1 0
0 -1 1
1 9
1 4
0 10
3 11
7 9
2 1 3
1 2 3
2 3 3
3 2 3
3 4 3
4 3 3
4 5 3
5 4 3

输出 #2

46

注意

在第一个样本中,f1(x) = x、f2(x) = x + 1 和 f3(x) = x + 2,因此我们要最大化生成级别的总和。限制条件为 x1 ≤ x2、x2 ≤ x3 和 x3 ≤ x1,从而得出 x1 = x2 = x3。最佳配置是 x1 = x2 = x3 = 2,其产生的输出为 9。

在第二个示例中,限制等于 |xi - xi + 1| ≤ 3(对于 1 ≤ i < n)。最佳配置之一是 x1 = 1、x2 = 4、x3 = 5、x4 = 8 和 x5 = 7。