Рабочее место участника

Предприятие "Авто-2010" выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из `n` деталей, пронумерованных от 1 до `n`, при этом деталь с номером `i` изготавливается за `p_i` секунд. Специфика предприятия "Авто-2010" заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор "Авто-2010" поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

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

Первая строка входного файла содержит число `n` (`1\ ≤\ n\ ≤\ 100\ 000`) — количество деталей двигателя. Вторая строка содержит `n` натуральных чисел `p_1,\ p_2,\ …,\ p_n`, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит `10^9` секунд.

Каждая из последующих `n` строк входного файла описывает характеристики производства деталей. Здесь `i`-я строка содержит число деталей `k_i`, которые требуется изготовить перед производством детали с номером `i`, а также их номера. Сумма всех чисел `k_i` не превосходит `200\ 000`.

Известно, что не существует циклических зависимостей в производстве деталей.

В первой строке выходного файла два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число `k` деталей, которые необходимо для этого произвести. Во второй строке выведите через пробел `k` чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали номер 1.

3
100 200 300
1 2
0
2 2 1

300 2
2 1

2
2 3
1 2
0

5 2
2 1

4
2 3 4 5
2 3 2
1 3
0
2 1 3

9 3
3 2 1