Ағаш — бұл циклдері жоқ, байланысқан, бағытталмаған граф.

Сізге $n$ төбеден тұратын ағаш берілген, және әрбір төбенің $v$ салмағы $w_v$ бар.

Төбенің кереметтігі оның көршілерінің салмақтарының қосындысына тең: $c_v=\sum _{u\in g[v]}{w}_u$, — мұндағы $g[v]$ — төбе $v$-нің көршілерінің тізімі.

Ағаштың кереметтігі — ерекше төбелердің кереметтіктерінің қосындысы. Ерекше төбелер — нөмірі $L$-ден $R$-ге дейінгі төбелер. Демек, ағаштың кереметтігі келесідей анықталады: $$C=\sum _{v=L}^R{c}_v.$$

Сізге келесі операцияны кез келген рет (соның ішінде 0 рет) орындауға рұқсат етіледі:

1. Кез келген төбе $v$-ны таңдау.

2. Төбе $v$-нің барлық көршілерінің $w_u$ мәндерін $g[v]$ тізімінде берілген ретпен циклдік ығыстыру. Яғни, егер $g[v]=[u_1,u_2,\dots ,u_k]$ болса, онда операциядан кейін:

   • Жаңа $w_{u_1}$ ескі $w_{u_2}$-ге тең болады,

   • $w_{u_2}$ ескі $w_{u_3}$-ке тең болады,

   • $\dots$,

   • $w_{u_k}$ ескі $w_{u_1}$-ге тең болады.

Есептің мақсат — осы операцияларды қолданып, ағаштың кереметтігі $C$ мәнін мүмкіндігінше ең үлкен ету.

Енгізу

Бірінші жолда бүтін сан $T$ ($1\le T\le 100$) — тестілер саны.

Әрбір тест келесі түрде берілген:

• Бірінші жолда бүтін сан $n$ ($1\le n\le 5\cdot {10}^3$) — ағаштағы төбелер саны.

• Келесі жолда $n$ бүтін сандары $w_1,w_2,\dots ,w_n$ ($0\le w_v\le {10}^9$) — төбелердің салмақтары.

• Одан кейін $n$ жол, мұнда $v$-ші жол алдымен бүтін сан $k_v$ ($0\le k_v<n$) — төбе $v$-нің көршілерінің саны, содан кейін $k_v$ бүтін сандар — көршілерінің тізімі.

• Соңғы жолда екі бүтін сан $L$ және $R$ ($1\le L\le R\le n$) — ерекше төбелердің нөмірлерін анықтайтын аралық.

Кепілденеді, барлық тестілер үшін $n$ сандарының қосындысы $5\cdot {10}^3$-тен аспайды және әрбір тест ағаш болып табылады.

Шығару

$T$ жолды шығарыңыз, әр жолда бір бүтін сан — сипатталған операцияларды орындау арқылы қол жеткізуге болатын ағаштың кереметтігі $C$-нің ең үлкен мәні.

Бағалау жүйесі

Бұл есепте $6$ ішкі есеп бар.

Мысалдар

Енгізу 1

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

Жауап 1

34
20

Ескертпелер

Бірінші мысалда жауап [$1,1,6,1$] тәртібімен орындалатын операциялардан кейін қол жеткізіледі.