Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Аргументы (задача C школьного тура (2014-2015))

Задачу добавил: alef

Успешно сдано решений: 17

Ограничение по времени - 2 секунды на тест,  по памяти - 256 мегабайт на тест

Потап тоже наблюдал за корабликами и думал, что всё-таки нужно уговорить мэра встретиться с журналистом. Потап уже придумал n аргументов, которые, по его мнению, могут способствовать согласию мэра встретиться с Перуном-Нечитайло.

Однако есть две проблемы. Во-первых, на изложение каждого аргумента Потапу требуется одна минута, а мэр Редисочкин не станет слушать Потапа дольше, чем k минут. Во-вторых, некоторые аргументы Потап может привести только, сформулировав некоторые другие аргументы. Впрочем, если некоторому аргументу непосредственно предшествует более одного аргумента, Потапу достаточно привести только один из них (любой, на его выбор), чтобы продолжить. Потап полагает, что лучше всего построить изложение в таком порядке, чтобы перед каждым аргументом был приведён непосредственно предшествующий ему, если таковой имеется.

Потап считает, что у аргумента #j есть «вес» aj, и теперь он хочет узнать — какой самый весомый аргумент он сможет привести мэру Редисочкину.

Гарантируется, что если некоторому аргументу #p предшествует (не обязательно непосредственно) аргумент #q, то аргумент #p не предшествует (не обязательно непосредственно) аргументу #q.

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

В первой строке содержатся целые числа n и k (1 ≤ n, k ≤ 100000) — количество имеющихся у Потапа аргументов и количество минут, которые его будет слушать мэр.

Во второй строке содержатся n натуральных чисел aj (1 ≤ aj ≤ 100000) через пробел; число, находящееся на позиции j, обозначает вес аргумента j.

Далее следуют n строк. В строке, имеющей номер #j в этой группе, содержатся номера аргументов, которые должны предшествовать аргументу с номером #j. Каждую строку завершает 0.

Гарантируется, что общее количество чисел в файле не превосходит 400002.

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

В первой строке выведите два целых числа w и t — номер самого весомого аргумента, который Потап успеет изложить, и минуту, на которой Потап его изложит.

Во второй строке выведите t целых чисел через пробел — номера аргументов в порядке их изложения до самого «весомого» аргумента включительно.

Если существует более одного решения, выведите любое.

Примеры входных и выходных данных

Входные данные - 1
18 4
4 3 7 1 5 1 3 2 8 6 2 7 10 8 4 3 2 3
2 3 0
0
0
1 0
1 7 0
0
6 0
6 0
5 4 0
5 0
8 0
10 11 0
10 9 0
4 7 0
12 14 0
13 15 0
0
17 0
Выходные данные - 1
9 4
2 1 4 9
Входные данные - 2
10 12
4 2 1 5 7 4 3 7 6 8
0
0
0
1 5 0
2 6 0
3 0
4 0
5 7 0
6 8 0
9 0
Выходные данные - 2
10 6
1 4 7 8 9 10

Сдать задачу

Задать вопрос жюри по этой задаче