Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Капитан Флинт и сокровище
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В погоне за очередным сокровищем капитан Флинт наткнулся на некоторую задачу, которая может быть связана с поиском сокровища, а может и не быть. Поэтому капитан Флинт поручил ее решение своим матросам и назначил огромное вознаграждение: целый один выходной день. Задача же звучит так...

Заданы массивы $$$a$$$ и $$$b$$$ длины $$$n$$$. Изначально, $$$ans$$$ равен $$$0$$$ и определена следующая операция:

  1. Выбрать позицию $$$i$$$ ($$$1 \le i \le n$$$);
  2. Добавить к $$$ans$$$ значение $$$a_i$$$;
  3. Если $$$b_i \neq -1$$$, то добавить к $$$a_{b_i}$$$ значение $$$a_i$$$;

Какой максимальный $$$ans$$$ можно получить, применив эту операцию к каждой позиции $$$i$$$ ($$$1 \le i \le n$$$) ровно один раз?

Дядя Богдан очень хочет получить вознаграждение и просит Вас помочь ему с решением задачи, а также предоставить порядок позиций, в котором нужно применять операцию выше.

Входные данные

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массивов $$$a$$$ и $$$b$$$.

Во второй строке каждого набора задано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$−10^6 \le a_i \le 10^6$$$).

В третьей строке каждого набора задано $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$ или $$$b_i = -1$$$).

Дополнительное ограничение: гарантируется, что для $$$i$$$ ($$$1 \le i \le n$$$) последовательность $$$b_i, b_{b_i}, b_{b_{b_i}}, \ldots$$$ не зациклится, то есть будет всегда оканчиваться на $$$-1$$$.

Выходные данные

В первой строке выведите одно целое число, максимальный $$$ans$$$, который можно получить.

Во второй строке опишите последовательность выполнения операций, чтобы получить этот максимальный ответ: $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$), где $$$p_i$$$ обозначает позицию, операция над которой выполняется $$$i$$$-й по порядку. Если существует несколько таких последовательностей, выведите любою из них.

Примеры
Входные данные
3
1 2 3
2 3 -1
Выходные данные
10
1 2 3
Входные данные
2
-1 100
2 -1
Выходные данные
99
2 1
Входные данные
10
-10 -1 2 2 5 -2 -3 -4 2 -6
-1 -1 2 2 -1 5 5 7 7 9
Выходные данные
-9
3 5 6 1 9 4 10 7 8 2