小红定义一棵树的权值为: 若一条简单路径 满足 是一个回文串。在所有这样的路径中，路径的长度的最大值是是该树的权值。 现在小红给定一棵结点总数为 的树和 'a','b','c',...,'z'每种字母的个数，保证所有个数之和恰好等于 。 你需要将每个字母填入一个树的结点，使得该树的权值最大，输出树的最大权值。

输入描述:

第一行输入一个长度为26的数组，表示每个字母的个数，保证总和为 。第二行输入一个整数 ，表示树的结点总数。接下来 行，每行输入两个整数 ，表示树的一条边。

输出描述:

输出一个整数，表示树的最大权值。