Задача Производство деталей

Описание

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

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

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

Формат входных данных

Первая строка входного файла содержит число n (1 <= n <= 100000) - количество деталей двигателя. Вторая строка содержит n натуральных чисел p ₁ , p ₂ ... p _n , определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 10 ⁹ секунд.

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

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

Формат выходных данных

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