Сеть компании Ас me

Компания Acme — известный в мире производитель кондитерских и макаронных изделий — решила наладить поставку и производство своей продукции в Сибири. Было решено, что сеть компании в Сибири будет включать небольшие заводы по производству продукции, региональные оптовые, а также мелкооптовые склады и точки розничной торговли. Продукция будет поступать с заводов (предприятия нулевого уровня) на оптовые склады (предприятия первого уровня), затем на мелкооптовые склады разных уровней (предприятия второго, третьего, четвертого уровня и т.д. до уровня N  – 1 включительно, по очереди) и, наконец, в точки розничной торговли, которые далее будем называть потребителями.

Потребительская цепочка — это последовательность предприятий с _i ( i = 0, 1, ... N – 1), где с _i — номер предприятия i -го уровня в цепочке. Затраты компании Acme на поддержание такой сети будут состоять из затрат на открытие необходимых предприятий и затрат на транспортировку продукции от предприятий к потребителям по потребительским цепочкам. Стоимость обслуживания одного потребителя — это суммарная стоимость транспортировки продукции по звеньям цепочки, то есть затраты компании на поддержание такой сети равны сумме стоимостей обслуживания всех потребителей и стоимостей открытия всех предприятий, задействованных в цепочках.

Потребительские цепочки для разных потребителей могут иметь общие предприятия. При этом в стоимость обслуживания такой сети входит стоимость транспортировки для каждого потребителя, в то время как за открытие одного предприятия фирма платит только один раз.

Ваша задача состоит в том, чтобы спланировать торговую сеть для компании Acme , затраты на поддержание которой были бы как можно меньше.

Входные данные (файл input . txt )

Все числа во входном файле разделены пробелами. В первой строке входного файла даны два положительных целых числа N и a _N ( N £ 10, a _N   £ 100), где N — количество уровней, a _N — число потребителей. Во второй строке задано N положительных целых чисел a _i ( a _i   £  100, i  = 0 ..  N   – 1), где a _i — количество предприятий уровня i . Предприятия уровня i занумерованы числами от 1 до a _i включительно.

В последующих N строках заданы стоимости открытия предприятий — неотрицательные целые числа, не превосходящие 10000. Здесь в строке с номером j ( j  =   3   ..   N  + 2) заданы a _{j – 3} числа, равные стоимостям открытия предприятий уровня j  – 3.

Далее во входном файле задано N блоков информации о транспортных расходах по очереди. Блок с номером j ( j = 1 ..  N ) содержит информацию о расходах на транспортировку продукции от предприятий уровня j  – 1 до предприятий уровня j (до потребителей в случае j  =  N ). Блок с номером j состоит из a _{j –1} строк, в каждой из которых заданы a _j неотрицательных целых числа, не превосходящих 10000. Внутри блока n -е число m -й строки равно стоимости транспортировки продукции от m -го предприятия уровня j  – 1 до n -го предприятия уровня j (до n -го потребителя в случае j = N ).

Выходные данные (файл output . txt )

Выходной файл должен состоять из a _N строк. В i -той строке ( i = 1 .. a _N ) должны быть записаны через пробел N номеров предприятий с уровня 0 по уровень N – 1 включительно, составляющих потребительскую цепочку потребителя i . Данный выбор потребительских цепочек должен обеспечивать как можно меньшие суммарные затраты компании на поддержку торговой сети.

Примеры