哇，一年一度的七夕节到啦,Ar老师和女朋友准备了一趟环球旅行，于是Ar老师打开了世界地图，选取了N个地方作为理想的旅游目的地，但是由于经费有限，他只能去K个地方玩耍，并且K个地点最好是连续的一条路线。同时为了取悦小女友，Ar老师给每个地方的美观度评了分（Vi<=1000000），Ar老师希望所去的景区的美观度之和最大。为了简化问题，Ar老师选取的N个地点构成了一个恰好都联通的树形图，而显然，Ar老师去的路线即为图上一条路径。请你帮忙找一个最好的方案，使得Ar老师所去的美观度之和最大，并且输出首尾结点。若没有这样的方案，输出“no solution”。

输入第一行包含两个整数，N和K（N<=10000,K <= N）

第二行包含N个整数，表示第i个地点的美观度（Vi<=1000000）

接下来N-1行，每行两个整数u,v表示结点u,v之间有一条连线(1<=u,v<=N)

输出美观度之和最大值，以及该路径的首尾结点（首尾结点要求先输出编号小的）

如果存在两条路径取到最大值，输出首尾结点字典序小的一条（如1 2；1 3，则输出1 2）

若不存在方案，输出no solution

PS：如果图上没有一条链长度为K，则不存在方案。

-rw-rw-rw-