Задача №114669. Бизнес-шоу
Дима находится на шоу от бизнесмена Петра под названием «Петр помогает простому парню поискать подработку». В этом шоу Диме предстоит пройтись по дорожке, которая является прямоугольником из \(3\) строк и \(n\) столбцов. В каждой строке все клетки пронумерованы от \(1\) до \(n\) слева направо.
На каждой клетке написано число \(a_{i,j}\). Изначально у Димы есть баланс, равный нулю, и когда Дима наступает на клетку в \(i\)-й строке и \(j\)-м столбце, его баланс меняется на \(a_{i,j}\) рублей. Баланс может становиться отрицательным.
Дима может заходить на любые клетки первой и третьей строки, но изначально клетки второй строки для него недоступны. Однако есть \(q\) предложений от бизнесмена Петра, которые могут сделать их доступными: \(i\)-е предложение позволяет разблокировать все клетки второй строки на отрезке с \(l_i\) по \(r_i\), заплатив за это \(k_i\) рублей (то есть, уменьшив баланс на \(k_i\)). Дима может воспользоваться любым количеством таких предложений, а также разблокировать одну и ту же клетку несколько раз.
Дима изначально стоит на клетке в первой строке и первом столбце и хочет попасть в клетку в третьей строке и \(n\)-м столбце. За один ход Дима может подвинуться на 1 вправо или вниз, то есть увеличить на 1 номер строки или столбца. Таким образом, всего в процессе пути Дима сделает \(n + 1\) ход, из которых \(n - 1\) будет по горизонтали и \(2\) по вертикали.
Выигрыш Димы будет равен финальному балансу после совершения всех ходов, то есть сумме чисел на всех посещённых клетках за вычетом стоимости всех использованных предложений. Ваша задача — определить максимальный возможный выигрыш Димы.
В первой строке даны два целых числа \(n\) и \(q\) (\(1 \le n, q \le 500\,000\)) — длина прямоугольника и число возможных отрезков для разблокировки.
В следующих трёх строках описываются числа в прямоугольнике, в \(i\)-й строке даны \(n\) целых чисел \(a_{i1}\), \(a_{i2}\), ..., \(a_{in}\) (\(-10^9 \le a_{ij} \le 10^9)\) — числа в \(i\)-й строке прямоугольника.
В следующих \(q\) строках описываются доступные предложения для разблокировки отрезков, в \(i\)-й из них даны три целых числа \(l_i\), \(r_i\) и \(k_i\) (\(1 \leq l_i \leq r_i \leq n\), \(1\leq k_i\leq 10^9\)) — границы \(i\)-го отрезка и стоимость разблокировки всех клеток \(i\)-го отрезка.
Выведите одно число — максимальный возможный выигрыш Димы.
В первом примере оптимально воспользоваться вторым предложением Петра за \(4\) рубля и пройти по клеткам \((1, 1)\), \((1, 2)\), \((1, 3)\), \((2, 3)\), \((3, 3)\), \((3, 4)\), заработав \(1 + 0 + 2 + 9 + 4 + 1 - 4 = 13\) рублей.
Во втором примере оптимально воспользоваться вторым и третьим предложением Петра за \(2\) и \(3\) рубля соответственно, и пройти по клеткам \((1, 1)\), \((2, 1)\), \((2, 2)\), \((2, 3)\), \((2, 4)\), \((3, 4)\), \((3, 5)\), заработав \(-20 + 1 + 3 + 3 + 6 + 6 + 2 - 2 - 3= -4\) рубля.
Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(q\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 10 | – | \(q=1\) | – | |
| 2 | 16 | \(n\leq 500\) | \(q\leq 500\) | 0 | |
| 3 | 14 | \(n\leq 2\,000\) | \(q\leq 5\,000\) | 0, 2 | |
| 4 | 17 | – | – | – | Все \(k_i\) одинаковы |
| 5 | 21 | \(n\leq 100\,000\) | \(q\leq 100\,000\) | 0, 2, 3 | |
| 6 | 22 | – | – | 0 – 5 | Offline-проверка. |
4 3 1 0 2 -1 -3 1 9 2 3 2 4 1 1 2 5 2 3 4 1 4 14
13
5 4 -20 -10 -11 -10 1 1 3 3 6 3 14 -20 3 6 2 1 5 13 1 2 2 3 5 3 2 3 1
-4