Рассмотрим лестницу, состоящую из \(n\) ступеней. Каждая ступень может быть целой или сломанной. Для каждой сломанной ступени задано целое число \(a_i\), обозначающее сложность ее ремонта.
Каждый день вы можете:
Вы хотите отремонтировать все сломанные ступени лестницы и сделать это за минимальное количество дней. Каково минимальное общее усилие, необходимое для ремонта всех сломанных ступеней за минимальное количество дней?
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.
Каждый набор входных данных состоит из двух строк:
Дополнительное ограничение на входные данные: сумма значений \(n\) не превышает \(3 \cdot 10^5\).
Для каждого набора входных данных выведите одно целое число — минимальное возможное общее усилие, необходимое для ремонта всех сломанных ступеней за минимальное количество дней.
В первом наборе входных данных вам ничего не нужно делать.
Во втором наборе входных данных вы можете отремонтировать \(3\)-ю и \(4\)-ю ступени в первый день, и \(2\)-ю ступень во второй день. Общее усилие будет равно \(2 \cdot (15 + 8) + 13 = 59\).
В третьем наборе входных данных вы можете отремонтировать \(4\)-ю ступень в первый день, и две первые ступени во второй день. Общее усилие будет равно \(8 + 2 \cdot (13 + 15) = 64\).
6 5 0 0 0 0 0 4 0 13 15 8 4 13 15 0 8 8 1 2 3 4 5 6 7 8 5 99999999 100000000 99999999 99999999 99999999 5 2 3 4 3 2
0 59 64 72 899999993 24
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач