题目内容

在一个工业园区内，有 $n$ 个采集点，它们之间由 $m$ 条道路连接。第 $i$ 个采集点完成一次采集需要耗时 $a_i$ 分钟，能够带来的收益为 $b_i$。每条道路的通行耗时 $w_i$ 分钟。

你拥有一辆无人车，单次任务的总可用时长为 $K$ 分钟。你希望在一次任务中选择至多三个采集点，并且这些采集点必须在道路网络中构成一个连通子图（可以是单个采集点、由一条道路直接相连的两个采集点、或者一个中心采集点及其两个不同的相邻采集点）。任务的总耗时等于选中的所有采集点的耗时之和，再加上必须经过的道路的通行耗时之和。你需要保证总耗时不超过 $K$。

请你计算在满足时间约束的前提下，能够获得的最大总收益。

数据范围：采集点的数量 $n$ 和道路的数量 $m$ 均不超过 $10^5$。总可用时长 $K$、每个采集点的耗时 $a_i$ 与收益 $b_i$、以及每条道路的通行耗时 $w_i$ 均为正整数且不超过 $10^9$。

输入描述