Вам дано \(n\) массивов, которые могут иметь разные длины. Также вам дана таблица с \(w\) столбцами и \(n\) строками. \(i\)-й массив горизонтально расположен в \(i\)-й строке. Вы можете двигать каждый массив внутри его строки, но он должен всегда занимать подряд идущие клетки и лежать полностью внутри таблицы.
Вам нужно найти наибольшую возможную сумму чисел в \(j\)-м столбце для каждого \(j\) от \(1\) до \(w\) независимо.
Обратите внимание, что вы можете исключить любой массив из столбца (но только если он останется внутри своей строки). В таком случае значение полагается равным нулю.
В первой строке ввода записано два целых числа \(n\) (\(1 \le n \le 10^{6}\)) и \(w\) (\(1 \le w \le 10^{6}\)) — количество массивов и ширина таблицы.
Каждая из следующих \(n\) строк содержит целое число \(l_{i}\) (\(1 \le l_{i} \le w\)) — длина \(i\)-го массива, за которой следуют \(l_{i}\) целых чисел \(a_{i1}, a_{i2}, \ldots, a_{il_i}\) (\(-10^{9} \le a_{ij} \le 10^{9}\)) — элементы массива.
Суммарная длина массивов не превосходит \(10^{6}\).
Выведите \(w\) целых чисел, \(i\)-е из них должно равно максимальной сумме для столбца \(i\).
Изображения для первого примера находятся в условии.
3 3 3 2 4 8 2 2 5 2 6 3
10 15 16
2 2 2 7 8 1 -8
7 8
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач