spioni

O reţea formată din $n$ spioni, numerotaţi de la $1$ la $n$, aflaţi în diferite localităţi, au o convenţie de convocare. Ei vor fi convocaţi telefonic într-o localitate fixă numită bază. Convenţia de transmitere a convocării cuprinde următoarele reguli:

• cu excepţia unora, fiecare spion ştie ce persoane trebuie să-l contacteze telefonic; pentru a considera convocarea validă şi a-i da curs, trebuie să primească semnalul de convocare de la toate persoanele de contact;
• cei câţiva spioni care nu aşteaptă nici o convocare ştiu că trebuie să pornească toţi deodată, la o oră considerată ora $0$, spre bază;
• fiecare persoană, imediat ce a ajuns la bază, primeşte lista persoanelor pe care trebuie să le sune, transmiţându-le convocarea;
• durata unei convorbiri telefonice este neglijabilă;
• abia în momentul în care sunt prezente toate cele $n$ persoane la bază poate să înceapă şedinţa.

Cerință

Cunoscându-se, pentru fiecare spion, durata deplasării până la bază (exprimată în ore) şi lista persoanelor care trebuie să îl contacteze, scrieţi un program care stabileşte dacă se poate realiza convocarea tuturor persoanelor. Dacă este posibil, să se determine:

1. numărul minim de ore care trec până când poate să înceapă şedinţa;
2. numărul minim de persoane care trebuie transportate în regim de urgenţă astfel încât şedinţa să poată începe cu cel puţin o oră mai devreme; numim transport în regim de urgenţă un transport în care, în locul timpului dat, transportul durează cu cel puţin o oră mai puţin;
3. numerele de ordine ale persoanelor care vor fi transportate în regim de urgenţă, afișate în ordine crescătoare.

Date de intrare

Fişierul de intrare spioni.in, conţine:

• pe prima linie, numărul $n$ de spioni;
• pe a doua linie, $n$ numere naturale $t_1, t_2, \dots, t_n$, despărţite prin câte un spaţiu, numere reprezentând durata deplasării fiecărui spion până la bază (în regim normal), durată exprimată în ore;
• pe fiecare dintre următoarele $n$ linii, numărul de persoane $m$ care trebuie să convoace persoana având numărul $i$, pentru ca aceasta să pornească spre bază, urmat de cele $m$ persoane.

Date de ieșire

Pe prima linie a fişierului spioni.out se află numărul $-1$ dacă nu se poate realiza convocarea, sau numărul de ore după care poate să înceapă şedinţa, în caz contrar.

În cazul în care convocarea este posibilă, fişierul mai conţine:

• pe a doua linie, un număr $p$, reprezentând numărul de persoane care, transportate în regim de urgenţă, pot devansa ora de începere a şedinţei cu cel puţin o oră;
• pe a treia linie, numerele de ordine ale persoanelor care trebuie să fie transportate în regim de urgenţă, pentru a putea începe şedinţa mai devreme, numere despărţite prin câte un spaţiu. Aceste numere trebuie afișate în ordine crescătoare.

Restricții și precizări

• $1 \le n \le 7\ 500$
• $\sum m \le 200\ 000$
• $2 \le t_i \le 10^9$
• Problema a fost modificată.
• Se acordă o treime din punctaj pentru prima cerință și restul în plus pe ultimele două cerințe.

Exemplu

spioni.in

5
9 8 3 9 2
0
0
0
3 1 3 5
2 2 3

spioni.out

19
1
5