Дима находится на шоу от бизнесмена Петра. В этом шоу Диме предстоит пройтись по дорожке, которая является прямоугольником \(3 \times n\), где строки пронумерованы от \(1\) до \(3\) сверху вниз, а столбцы от \(1\) до \(n\) слева направо.
На клетке на пересечении строки \(i\) и столбца \(j\) написано число \(a_{i,j}\). Изначально у Димы есть баланс, равный нулю, и когда Дима наступает на клетку в \(i\)-й строке и \(j\)-м столбце, его баланс меняется на \(a_{i,j}\) рублей. Баланс может становиться отрицательным.
Дима может заходить на любые клетки первой и третьей строки, но изначально клетки второй строки для него недоступны. Однако есть \(q\) предложений от бизнесмена Петра, которые могут сделать их доступными: \(i\)-е предложение позволяет разблокировать все клетки второй строки на отрезке с \(l_i\) по \(r_i\), заплатив за это \(k_i\) рублей. Дима может воспользоваться любым количеством таких предложений, а также разблокировать одну и ту же клетку несколько раз.
Дима изначально стоит на клетке в клетке \((1, 1)\) и хочет попасть в клетку \((3, n)\). За один ход Дима может подвинуться на 1 вправо или вниз, то есть увеличить на 1 номер строки или столбца. Таким образом, всего в процессе пути Дима сделает \(n + 1\) ход, из которых ровно \(n - 1\) будет по горизонтали и \(2\) по вертикали.
Выигрыш Димы будет равен финальному балансу после совершения всех ходов, то есть сумме чисел на всех посещённых клетках за вычетом стоимости всех использованных предложений. Ваша задача — определить максимальный возможный выигрыш Димы.
Выходные данные
Выведите одно число — максимальный возможный выигрыш Димы.
Примечание
В первом примере оптимально воспользоваться вторым предложением Петра за \(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\) рубля.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 0 2 -1
-3 1 9 2
3 2 4 1
1 2 5
2 3 4
1 4 14
|
13
|
|
2
|
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
|