P3874 [TJOI2010] 砍树

小 A 在果园里发现了一棵结满果子的树，于是他就打起了坏主意，他打算把树的一部分砍下来带回家。

我们可以把这棵树表示成一个树型的结构，也就是说，任意两个点之间有且仅有一条路径。在每个点 $i$ 处都结着一个水果，每个水果有一个价值 $v_i$ 和重量 $w_i$。小 A 想带走树的一部分（或全部），包含至少 $K$ 个结点（也就是至少 $K$ 个水果），且这些水果的平均价值尽可能高。平均价值是指水果总的价值除以总的重量。注意小 A 砍下的树必须是在原来的树中连通的一部分。

无

无

### 数据规模与约定 - 对 $20\%$ 的数据，$1 \le N \le 16$； - 对 $100\%$ 的数据，$1 \le N \le 100$，$1 \le K \le N$，$1 \le v_i \le 10000$，$1 \le w_i \le 10000$。