Felicidade Suprema

#13

Made by: Luiz H. Lago

1000MB

Brizzi é um estudante de CC da UFSM, e utiliza tanto o Spotify quanto o YouTube para ouvir música. No Spotify, ele pode salvar suas músicas preferidas em playlists e álbuns, mas prefere usar o YouTube para descobrir novas músicas que não conhece, pois acha que seu sistema de recomendação é muito superior ao do Spotify. Ele sempre começa com uma música que conhece e gosta muito, e ao final de cada música, são mostradas várias novas opções na aba "Para assistir a seguir", algumas que agradam mais ou menos ao Brizzi.

Ultimamente, o algoritmo do YouTube tem decepcionado Brizzi, mostrando músicas que nem sempre o agradam, o que o deixa um pouco triste. Por conta disso, Brizzi está curioso para saber se há alguma forma de otimizar sua busca por músicas e sempre aumentar sua felicidade para alcançar o "Panteao da felicidade suprema".

Brizzi então separou em uma lista cada música existente e atribuiu a elas uma pontuação de felicidade que ele ganha ao ouvi-las, podendo ser positiva ou negativa, e também identificou quais músicas são recomendadas ao final de cada uma. Ele quer descobrir por qual música deve começar para obter o máximo de felicidade possível, e qual seria o valor dessa felicidade ao selecionar apenas as músicas recomendadas. Brizzi respeita os artistas de todos os gêneros musicais, então sempre ouve uma música até o final, mesmo que isso lhe cause angústia e desespero. Além disso, não se importa em repetir músicas, desde que isso lhe proporcione mais felicidade.

Input

Na primeira linha será dado um valor $N$ $(1<= N <=3 \times 10^3)$, representando a quantidade de músicas. Na linha seguinte serão dados os $N$ números inteiros ($a_1$,$a_2$,...,$a_i$) $(-1\times(2^{16})<a_i<2^{16})$, representando o valor de felicidade para cada música $i$ $(1 <= i <= N)$.

Para cada música $i$ de 1 até $N$ haverá um bloco de duas linhas. A primeira linha, tem o número $L_i$ $(0 <= L_i <= N)$ de músicas recomendadas ao final da música $i$. A segunda linha contém $L_i$ valores distintos representando quais são as músicas recomendadas pela música $i$.

Output

Escrever na tela um valor $i$ dizendo por qual música Brizzi deve começar, e o máximo de felicidade que ele vai conseguir se seguir o melhor caminho. Se existirem mais de uma resposta com o mesmo valor, o menor $i$ deve ser printado.

Se for possível Brizzi atingir um caminho de felicidade infinita, ele poderá ascender aos céus, então deve ser impresso o texto "Panteao da felicidade suprema" no lugar do valor máximo de felicidade.

Input Example

Output Example

8
-6 -5 -7 -6 -2 -1 10 10
3
2 4 7
2
3 8
0

1
6
1
2
1
5
1
6
1
4

7 12

10
-1 -4 5 -6 -4 -6 -5 4 -3 2
3
2 9 10
1
3
3
4 5 9
2
3 3
4
1 2 4 6
3
7 7 8
6
2 5 6 8 9 9
1
5
3
1 2 5
1
7

3 5

10
-2 5 4 1 -3 -1 4 3 6 -4
3
4 9 10
1
6
2
1 1
2
3 7
1
6
0

4
1 6 8 10
3
2 5 6
5
1 2 2 5 8
1
8

Panteao da felicidade suprema

6
-5 6 -3 1 6 -3
2
2 6
1
6
2
4 5
2
1 5
0

1
3

2 7