Chloe 和 Vladik 参加的奥运会的慷慨赞助商允许所有参赛者自行为他们选择奖品。圣诞节即将到来,赞助商决定用他们的奖品来装饰圣诞树。
他们为参赛者颁发了n个奖品,并在每个奖品上写下了一个唯一的id(从1到n的整数)。礼物 i 的特征是整数 ai——礼物的愉快程度。礼物的愉悦感可以是正值、负值或零。赞助商将礼物 1 放在树顶。所有其他礼物都挂在与其他礼物绑在一起的绳子上,以便每件礼物都挂在第一个礼物上,可能还有一系列绳子和其他礼物。形式上,这些礼物形成了一棵有 n 个顶点的有根树。
颁奖程序是这样的:参与者陆续来到树前,选择剩余的礼物中的任何一个,并剪断奖品所挂的绳子。请注意,用于将其他奖品挂在所选奖品上的所有绳子都不会被切断。因此,参赛者会获得所选的礼物以及挂在上面的所有礼物,可能还有一系列绳子和其他礼物。
我们的朋友Chloe和Vladik分享了奥林匹克竞赛第一名,他们将同时评选奖品!为了避免打架,他们决定选择两件不同的礼物,这样用一系列绳子挂在他们身上的礼物和另一件礼物就不会相交。换句话说,不应该有任何礼物同时挂在Chloe选择的礼物和Vladik选择的礼物上。他们将从所有可能的变体中选择这样一对奖品,使得他们在割断绳子后获得的所有礼物的愉悦感之和尽可能大。
打印 Vladik 和 Chloe 可以获得的最大愉悦度总和。如果他们不可能在不战斗的情况下选择礼物,请打印“不可能”。
输入
第一行包含一个整数 n (1 ≤ n ≤ 2·105) – 礼物的数量。
下一行包含 n 个整数 a1, a2, ..., an ( - 109 ≤ ai ≤ 109) – 礼物的愉快程度。
接下来的 (n - 1) 行每行包含两个数字。这些行的第 i 行包含整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 树边的描述。这意味着编号为 ui 和 vi 的礼物用绳子相互连接。绳索描述中的礼物 ID 可以按任意顺序给出:vi 挂在 ui 上或 ui 挂在 vi 上。
保证所有礼物都挂在第一个礼物上,可能还有一系列绳子和另一个礼物。
输出
如果 Chloe 和 Vladik 可以在不打斗的情况下选择奖品,请打印单个整数——他们可以在一起的最大可能的愉快程度。
否则打印不可能。
示例
输入 #1
8 0 5 -1 4 3 2 6 5 1 2 2 4 2 5 1 3 3 6 6 7 6 8
输出 #1
25
输入 #2
4 1 -5 1 1 1 2 1 4 2 3
输出 #2
2
输入 #3
1 -1
输出 #3
Impossible