为了保护环境，p6pou建设了一个垃圾分类器。

垃圾分类器是一个树形结构，由 \(n\) 个垃圾桶和 \(n-1\) 条双向传送带组成。垃圾处理器的编号为 \(1,2,\dots,n\) ，每条传送带都可以花 \(1\) 秒钟将垃圾从一个垃圾桶输送到另一个垃圾桶。垃圾投放点是编号为 \(r\) 的垃圾桶，垃圾总是投放在这里。

垃圾共有 \(n\) 种，编号也是 \(1,2,\dots,n\) 。编号为 \(i\) 的垃圾会被输送到编号为 \(i\) 的垃圾桶里面，垃圾总是自动沿着最短路线输送，到达编号为 \(i\) 的垃圾桶后需要 \(a_i\) 秒才能被垃圾桶处理完成。为了避免不同垃圾混在一起，p6pou将垃圾按照编号从小到大的顺序依次投入编号为 \(r\) 的垃圾桶，每投放一种垃圾之后，必须等到这种垃圾被输送到其他垃圾桶，或者被编号为 \(r\) 的垃圾桶处理完成，才能继续投放下一种垃圾。传送带输送垃圾也一样，如果要将垃圾从编号为 \(x\) 的垃圾桶中的垃圾传输到编号为 \(y\) 的垃圾桶，如果此时编号为 \(y\) 的垃圾桶中有另一种垃圾，必须等到另一种垃圾被传输走或者被处理完成后才能传输。

现在p6pou想知道，开始投放垃圾到垃圾分类器处理完所有所有垃圾，总共需要花费多长时间。

第一行两个整数 \(n,r\) ，垃圾种类和垃圾桶数量都是 \(n\) ，垃圾投放点是编号为 \(r\) 的垃圾桶。

第二行 \(n\) 个整数 \(a_1,a_2,\dots,a_n\) ，表示第 \(i\) 个垃圾桶处理第 \(i\) 种垃圾的时间。

接下来 \(n-1\) 行每行两个数 \(x,y\) ，表示有一条双向传送带连接编号为 \(x,y\) 的两个垃圾桶。

输出一个整数，表示从开始投放垃圾到处理完所有垃圾的总时间。

样例说明1
开始投放 \(2\) 秒后， \(1\) 号垃圾到达 \(1\) 号垃圾桶， \(2\) 号垃圾到达 \(2\) 号垃圾桶， \(3\) 号垃圾还没投放；
开始投放 \(4\) 秒后， \(2\) 号垃圾处理完成；
开始投放 \(5\) 秒后， \(3\) 号垃圾到达 \(2\) 号垃圾桶，此时 \(1\) 号垃圾桶仍在处理 \(1\) 号垃圾，所以 \(3\) 号垃圾无法传输，在此等待；
开始投放 \(7\) 秒后， \(1\) 号垃圾处理完成；
开始投放 \(9\) 秒后， \(3\) 号垃圾到达 \(3\) 号垃圾桶；
开始投放 \(14\) 秒后， \(3\) 号垃圾处理完成。此时，所有垃圾都已经处理完。

样例说明2
开始投放 \(9\) 秒后， \(1\) 号垃圾处理完；
开始投放 \(8\) 秒后， \(2\) 号垃圾处理完；
开始投放 \(14\) 秒后， \(3\) 号垃圾处理完；
开始投放 \(12\) 秒后， \(4\) 号垃圾处理完；
开始投放 \(16\) 秒后， \(5\) 号垃圾处理完；
开始投放 \(18\) 秒后， \(6\) 号垃圾处理完。

数据规模与约定
对于 \(20\%\) 的数据， \(n\leq 100\) ；
对于 \(40\%\) 的数据， \(n\leq 1000\) ；
对于另外 \(20\%\) 的数据，垃圾分类器的树形结构是一条链，垃圾投放点是链的一个端点；
对于另外另外 \(20\%\) 的数据， \(a_1,\dots,a_n\) 都相等。
对于 \(100\%\) 的数据， \(n\leq 100000, 0\leq a_i\leq10^9, 1\leq x,y\leq n\) 。

此题的简化版2767