U503785 红题？

在一个被自然灾害严重破坏的地区，有多个受灾点和一个救援中心。救援中心拥有有限的救援物资，需要将这些物资合理分配到各个受灾点，以最大程度地减少受灾群众的损失。由于道路受损严重，救援车辆只能沿着特定的路径行驶，并且每个受灾点对物资的需求量和接收能力各不相同。为了高效地进行物资分配，救援团队决定使用一种高效的算法来确定最佳的物资分配方案。

给定一个无向图，表示救援中心（节点 $0$）和各个受灾点（节点 $1$ 到 $N-1$）之间的连接情况。图中的每条边有一个通行时间，表示车辆通过该边所需的时间。每个受灾点有一个物资需求量和一个最大接收能力（即最多能接收多少物资）。救援中心有 $M$ 个单位的物资。 现在，救援团队需要在有限的时间内（$T$）内，尽可能地将物资分配到各个受灾点，使得满足的物资需求量最大化。每个受灾点只能由一辆车访问一次，并且车辆必须回到救援中心。 你需要编写一个程序，计算在给定的时间内，能够满足的最大物资需求量。

第一行包含四个整数 $N, M, T，$分别表示节点数（受灾点和救援中心总数），救援物资的总量，以及最大可用时间。 接下来 $N-1$ 行，每行包含三个整数 $u, v, w$，表示节点 $u$ 和节点 $v$ 之间有一条边，通行时间为 $w$。 接下来 N 行，每行包含两个整数 $need$ 和 $capacity$，分别表示节点$i$（节点编号从 $1$ 开始）的物资需求量和最大接收能力。

输出一个整数，表示在给定时间内，能够满足的最大物资需求量。

# 数据范围 $2≤N≤100$ $1≤M≤1000$ $1≤T≤10000$ $1≤u,v