Обозначим оценку массива \(b\) с \(k\) элементами как \(\sum_{i=1}^{k}\left(\sum_{j=1}^ib_j\right)\). Иными словами, пусть \(S_i\) обозначает сумму первых \(i\) элементов массива \(b\). Тогда оценка может быть записана как \(S_1+S_2+\ldots+S_k\).
Скибидусу даны \(n\) массивов \(a_1,a_2,\ldots,a_n\), каждый из которых содержит \(m\) элементов. Будучи тем самым сигмой, он хотел бы объединить их в любом порядке, чтобы получить один массив, содержащий \(n\cdot m\) элементов. Пожалуйста, найдите максимальную возможную оценку, которую Скибидус может достичь с помощью своего объединенного массива!
Формально, среди всех возможных перестановок\(^{\text{∗}}\) \(p\) длины \(n\), выведите максимальную оценку для \(a_{p_1} + a_{p_2} + \dots + a_{p_n}\), где \(+\) обозначает объединение\(^{\text{†}}\).
Выходные данные
Для каждого набора входных данных выведите максимальную оценку среди всех возможных перестановок \(p\) на новой строке.
Примечание
Для первого набора входных данных есть две возможности для \(p\):
- \(p = [1, 2]\). Тогда \(a_{p_1} + a_{p_2} = [4, 4, 6, 1]\). Его оценка равна \(4+(4+4)+(4+4+6)+(4+4+6+1)=41\).
- \(p = [2, 1]\). Тогда \(a_{p_1} + a_{p_2} = [6, 1, 4, 4]\). Его оценка равна \(6+(6+1)+(6+1+4)+(6+1+4+4)=39\).
Максимально возможная оценка равна \(41\).
Во втором наборе входных данных одна из оптимальных расстановок окончательного объединенного массива: \([4,1,2,1,2,2,2,2,3,2,1,2]\). Мы можем вычислить, что оценка равна \(162\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 2
4 4
6 1
3 4
2 2 2 2
3 2 1 2
4 1 2 1
2 3
3 4 5
1 1 9
|
41
162
72
|