2074. Хоббит, или Туда и обратно

Бильбо вернулся домой после необычного путешествия и решил написать об этом книгу с названием "Алая книга Западных пределов". Во время своего путешествия он побывал в пещерах под Мглистым хребтом, в тюрьме эльфов Лихолесья, встретил дракона на Одинокой горе и побывал во многих переделках.

Всего Бильбо побывал в `n` интересных местах. Все интересные места, а также его дом находятся на одной прямой. Его дом находится на прямой в точке с координатой `0`, а `i`-ое интересное место удалено от дома Бильбо на `x_i` километров. Между каждой парой интересных мест `i` и `j` есть скрытый путь, который не проходит через другие интересные места. Длина этого пути равна `|x_j\ -\ x_i|`, а опасность равна `c_{i,j}`. Между `i`-ым интересным местом и домом также есть скрытый путь, длина которого – `x_i`, а опасность – `0`.

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

Первая строка входного файла содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 1000`) – количество интересных мест. Во второй строке дано `n` чисел `x_i` (`1\ ≤\ x_i\ ≤\ 10^9`), где `x_i` – удаленность `i`-того места от дома Бильбо в километрах. Все `x_i` различны.

В каждой из следующих `n` строчек содержится по `n` чисел. `j`-ое число в `i`-ой строчке – `c_{i,j}`, опасность скрытого пути между местами `i` и `j` (`0\ ≤\ c_{i,j}\ ≤\ 10^6`, `c_{i,j}\ =\ c_{j,i}`, `c_{i,i}\ =\ 0`).

В первой строке выведите два числа – длину и опасность пути Бильбо. Во второй строке выведите `n` чисел – номера интересных мест в порядке посещения.

3
1 2 3
0 10 1
10 0 1
1 1 0

6 2
1 3 2