Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Электростанция Нанами
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нанами любит играть в игры, и у нее это шикарно получается. Сегодня она играла в новую игру, требующую управления электростанцией. Задача Нанами — следить за генераторами завода и получать максимальную производительность.

На заводе есть n генераторов. Каждому генератору надо установить определенный уровень работы. Уровень работы генератора — это целое число (возможно, равное нулю или отрицательное), при этом уровень i-го генератора должен быть между li и ri (обе границы включительно). Производительность генератора зависит от уровня работы генератора x как квадратичная функция f(x). Каждый генератор имеет свою функцию производительности, функция i-го генератора fi(x).

Однако есть еще m ограничений на уровни генераторов. Пусть уровень i-го генератора равен xi. Каждое ограничение имеет вид: xu ≤ xv + d, где u и v — идентификаторы двух различных генераторов, а 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.

Выходные данные

Выведите единственную строку, содержащую единственное целое число — максимальную производительность всех генераторов. Гарантируется, что существует хотя бы одна корректна конфигурация.

Примеры
Входные данные
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
Выходные данные
9
Входные данные
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
Выходные данные
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.