29327번 - Хоббит, или Туда и обратно 스페셜 저지다국어

문제

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

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

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

입력

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

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

출력

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

제한

힌트