A. Берландийн Уурхайчид

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Берландийн хамгийн том алтны уурхай нь $n$ хонгилоос тогтох ба тэдгээр хонгилууд нь хоорондоо $n - 1$ холбоосоор холбогддог. Уурхайн хаалга нь $1$ дугаартай хонгилтой холбогдсон ба эндээс холбоосуудаар дамжин бусад бүх хонгил руу очих боломжтой.

$k$ ажилчинтай InMine корпораци уурхайг ажилуулдаг. Өдөр бүр корпораци ажилчидаа ангилан хонгил руу явуулдаг ба хонгил бүрд хамгийн ихдээ нэг ажилчин ажилдаг.

Бид бүх хонгилын таазны өндөрийг $h_{i}$ метр, бүх уурхайчдын өндөр $s_{j}$ метр гэдгийг мэднэ. Хэрвээ уурхайчны өндөр нь байгаа хонгилын таазны өндөрөөс хэтрэхгүй байвал тэр тухтай зогсож чаддаг, эсрэг тохиолдолд зогсох нь түүнд хэцүү байдаг.

Уурхайчид Берландад ажил хаялт зарлажээ, тиймээс InMine корпораци уурхайчдад тэдний ажлийн орчинг сайжруулах талаар боломжит бүх оролдлогыг хийхээр болжээ. Уурхайчдыг ажил хаялт зарлуулахгүй байлгахын тулд ямар ч уурхайчин хаалганаас өөрийн ажилдаг хонгил хүртэлх аль ч хэсэгт тонгоохгүй байх(мөн өөрийн ажилладаг хонгилдоо тухтай зогсох боломжтой байх) ёстой юм.

Энэ зорилгод хүрэхийн тулд та яг нэг хонгилыг сонгож аваад түүнийхээ таазны өндөрийг цөөн хэдэн метрээр ихэсгэх юм. Хонгилыг томсгох ажил нь зардал ихтэй ба нарийн төвөгтэй ажил учраас InMine корпораци танаас бүх уурхайчдыг ажилж байгаа орчиндоо тухтай байхаар тэднийг хонгилуудад хуваарилах боломжтой байлгахын тулд хонгилын таазыг хамгийн багадаа хэдэн метрээр өндөр болгох хэрэгтэй вэ эсвэл энэ нь боломжгүй юу гэдгийг тодорхойлж өгөхийг хүсчээ.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($1 ≤ n ≤ 5*10^{5}$) -- уурхайн хонгилын тоо байрлана.

Дараагийн мөрөнд $n$ ш эерэг бүхэл тоо $h_{1}, h_{2}, ..., h_{n}$ ($1 ≤ h_{i} ≤ 10^{9}$), $h_{i}$ нь $i$-дахь хонгилын таазны өндөр.

Дараагийн $n - 1$ мөрөнд хонгилуудын холбоосын тодорхойлот байрлана. Мөр бүр $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$) хэлбэртэй байна. $a_{i}$, $b_{i}$ нь хоорондоо холбоосоор холбогдсон хонгилуудын дугаар юм.

Дараагийн мөр бүхэл тоо $k$ ($1 ≤ k ≤ n$) агуулна.

Сүүлийн мөр $k$ ширхэг бүхэл тоо $s_{1}, s_{2}, ..., s_{k}$ ($1 ≤ s_{j} ≤ 10^{9}$) агуулах ба $s_{j}$ нь $j$-дахь уурхайчны өндөр юм.

Гаралт

Нэг мөрөнд уурхайчдыг ажлын орчиндоо тухтай байхаар хувааж болдог байхаар хонгилын таазыг өндөрсгөх хэмжээний хамгийн бага утга болох хэмжээг метрээр хэвлэ. Хэрвээ энэ нь боломжгүй бол $ - 1$ гэж хэвлэ. Хэрвээ эхэндээ ямар ч хонгилын таазыг өндөрсгөх шаардлагагүй байвал $0$-ийг хэвлэ.

Орчуулсан: Жавхлан

Жишээ тэстүүд

Оролт
6
5 8 4 6 3 12
1 2
1 3
4 2
2 5
6 3
6
7 4 2 5 3 11
Гаралт
6
Оролт
7
10 14 7 12 4 50 1
1 2
2 3
2 4
5 1
6 5
1 7
6
7 3 4 8 8 10
Гаралт
0
Оролт
3
4 2 8
1 2
1 3
2
17 15
Гаралт
-1

Тэмдэглэл

Эхний жишээ тестэнд бид 1-р хонгилын таазыг $5$-аас $11$ болгож өндөрлөх хэрэгтэй. Үүний дараа бид уурхайчдыг дараах байдлаар хуваарилаж чадна (эхлээд уурхайчны дугаар, дараа нь хонгилын дугаар): .

Хоёр дахь жишээ тестэнд дараах байдлаар хуваарилах боломжтой учир ямар нэг хонгилын таазын өндөрлөх шаардлагагүй: .

Гурав дахь жишээ тест боломжгүй.

Сэтгэгдлүүдийг ачааллаж байна...