介绍

根据群友的描述，这是一场pdd内推的笔试。参加的人数少，但是难度不低

题目内容

塔子哥生活在美丽的华光林，他非常喜欢这里的环境和氛围。在平常的休息时间，他会在家附近散步，欣赏美景，感受大自然的魅力。顺便会投喂经过遇到的小马们，让它们感受到人类的温暖和关爱。这样的生活让他感到非常满足和幸福。已知华光林共有 $N$ 个广场(分别编号 $1$ ~ $N$ ，塔子哥住在 $1$ 号广场)，以及有 $N-1$ 条道路，保证广场两两之间相互连通，且只有唯一一条通路， 且已知第 $i$ 个广场有 $A_i$ 只马。

塔子哥平时散步的时候有以下这些习惯：

1. 任意一个广场不能两次访问
2. 塔子哥的背包只能装下最多$M$份马粮
3. $1$ 份马粮只能投喂 $1$ 只马
4. 若要经过某个广场则要投喂其中所有的马(^. w .^)

塔子哥想知道，应当如何选择路线使得能投喂到最多数量的广场，且需要的马粮数量最少。

输入描述

第一行，两个整数 $N$ 和 $M$ ，分别表示华光林广场的数量，和准备带出门的马粮的份数( $1\le N\le 50,000$ ， $0\le M\le 5,000,000$ )

第二行，共 $N$ 个整数，其中第 $i$ 个整数 $A_i$ 表示第 $i$ 个广场的马的数量。( $0\le A_i \le 100$ )

接下来 $N-1$ 行，每行两个整数 $X$ 和 $Y$ ，表示编号 $X$ 和 $Y$ 的广场之间存在一条道路。( $1\le X,Y\le N$ )

输出描述

共一行，两个整数，分别表示：能投喂最多数量的广场，以及在此情况下需要最少多少马粮。

样例

样例一：

输入

2 1
2 1
1 2

输出

0 0

样例解释

塔子哥只有 $1$ 份马粮，小于 $1$ 号广场的马马数量，因此塔子哥决定不出门喂马。(T V T)

没有任何一个广场的马咪被投喂，也就不需要任何马粮。

样例二：

输入

3 4
1 2 3
1 2
2 3

输出

2 3