英雄救美
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

勇者小 A 来到了一座神奇的迷宫，里面藏着一把强大的传说武器，只要能拿到这把神器就能打败恶龙救出公主从此走上人生巅峰！
小 A 来到迷宫前查过攻略了，所以自信心爆棚，攻略上说：
这个迷宫其实是一个以 1 为根的二叉树，而且只能一左一右的往下移动（比如上一次你向左走了，那么这一次只能向右走），每个格子有一个魔法能量 w ，当你移动到这个格子后就能获得对应的魔法能量，你从根出发，现在你需要做的就是找到能使你获得能量最大的路径，那个路径的最后一个格子 (即叶子节点) 就是迷宫的出口！同时还要知道你一共能得到的最大能量是多少。

但是由于攻略的出现使得迷宫变的非常简单，所以有一股神秘的力量将迷宫更新啦！现在这个迷宫是可以旋转 m 次，比如当你移动到一个新的格子，你可以把左子树和右子树交换，这样左子树就变成了右子树，右子树就变成了左子树。(出口一定在叶子节点上，并且数据保证有解)
这下小 A 又懵啦，不得已，只能由你来帮助小 A 了！

输入描述:

第一行两个个整数 ，表示迷宫的格子数n和可旋转次数m;
第二行 n 个整数，表示第i个格子的魔法能力是 w 
接下来  n-1  行，每行三个整数 u,v,st ，st  为  1  表示 v 是 u 的左孩子，2 表示 v 是 u 的右孩子;

输出描述:

一共两行，第一行表示出口的格子编号，第二行表示能获得的最大能量.
(如果有多个格子都有可能是出口，输出编号最小的那一个)
示例1

输入

复制 
5 1
2 6 3 2 4
1 2 1
1 3 2
2 4 1
3 5 1

输出

复制 
4
10

说明