Нанами любит играть в игры, и у нее это шикарно получается. Сегодня она играла в новую игру, требующую управления электростанцией. Задача Нанами — следить за генераторами завода и получать максимальную производительность.
На заводе есть n генераторов. Каждому генератору надо установить определенный уровень работы. Уровень работы генератора — это целое число (возможно, равное нулю или отрицательное), при этом уровень i-го генератора должен быть между li и ri (обе границы включительно). Производительность генератора зависит от уровня работы генератора x как квадратичная функция f(x). Каждый генератор имеет свою функцию производительности, функция i-го генератора fi(x).
Однако есть еще m ограничений на уровни генераторов. Пусть уровень i-го генератора равен xi. Каждое ограничение имеет вид: xu ≤ xv + d, где u и v — идентификаторы двух различных генераторов, а d — целое число.
Игра показалась Нанами скучной, но сдаваться не в ее правилах. Поэтому она решила написать программу, которая посчитает для нее оптимальный ответ (максимально-возможную суммарную производительность). Как ни странно, в итоге работа по написанию программы досталась вам.
Выходные данные
Выведите единственную строку, содержащую единственное целое число — максимальную производительность всех генераторов. Гарантируется, что существует хотя бы одна корректна конфигурация.
Примечание
В первом примере 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.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|
46
|