L 国有 n 个城市,它们之间有 n-1 条道路,形成了一棵树的结构。
国王 L 派遣了一些军队来驻守这些道路,驻守每一条道路的军队战斗力都可以被量化为 [1,m] 中的整数。
每个城市都有一个城主,第 i 个城主有一个忍耐度 a_i。如果国王 L 在与第 i 个城市直接相连的所有道路上驻守的军队战斗力的中位数超过了城主的忍耐度,那么城主就会认为国王不信任他而产生谋反的心理。
国王 L 当然不希望有人造反,但他又想使驻守道路的军队的总战斗力最大来保证国防安全。现在他找到了 L 国最强的 OIer —— 您,去来帮助他解决这个问题。
如果无论如何安排军队都会有人想要造反,那么输出 -1。
注:对于任意 k 个数,它们的中位数是将这些数从小到大排序后第 \left\lfloor\dfrac{k}{2}\right\rfloor+1 个数。
