Максимальні суми підмасивів#12917

Максимальні суми підмасивів

Для масиву цілих чисел визначимо як найбільшу суму елементів будь-якого з його послідовних підмасивів (можливо, порожнього). Наприклад, f([-1, -2, -1]) = 0, а f([1, -2, 3, 1, -2, 1]) дорівнює , що досягається на .

Також, для двох масивів визначимо concat(a, b) як їхню конкатенацію. Наприклад, concat([1, 3], [2, 4]) = [1, 3, 2, 4]).

Вам надано масивів arr_1, arr_2, \ldots, arr_n. Знайдіть суму f(concat(arr_i, arr_j)) по всіх парах цілих чисел з 1 \leq i, j \leq n.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^4)  — кількість тестових наборів. Далі йде опис тестових наборів.

Перший рядок кожного тестового набору містить одне ціле число (1 \leq n \leq 4\cdot 10^5)  — кількість масивів.

-й з наступних рядків містить ціле число k_i та k_i цілих чисел arr_{i, 1}, arr_{i, 2}, \ldots, arr_{i, k_i} (1 \leq k_i \leq 4\cdot 10^5, -10^7 \leq arr_{i, j} \leq 10^7)  — довжину arr_i та його елементи.

Гарантується, що сума довжин усіх масивів у всіх тестових наборах не перевищує 4\cdot 10^5.

Вихідні дані

Для кожного тестового набору виведіть одне ціле число  — суму f(concat(arr_i, arr_j)) по всіх парах цілих чисел з 1 \leq i, j \leq n.

Приклади

Приклад

Loading
Loading

Примітка

У першому тестовому наборі необхідно знайти суму наступних підмасивів: f([1, 1, -10, 1, 1, -10]) = 2, f([1, 1, -10, 2, 2]) = 4, f([2, 2, 1, 1, -10]) = 6, f([2, 2, 2, 2]) = 8.

Загальна сума дорівнює 2 + 4 + 6 + 8 = 20.