小红正在给一套网络安全智能体做离线回放分析。系统会把每个基站在某一时刻采集到的异常流量记录成一个点,包含它的坐标、时间戳、负载值以及服务用户数。 如果两个基站的曼哈顿距离不超过给定阈值 `dist`,小红就认为它们在空间上可以直接联动。 对任意一个基站,若把它自己以及所有与它直接联动的基站的负载值 `w` 全部加起来,得到的总和不小于 `Wthreshold`,那么这个基站会被标记为一个关键节点。 接下来,小红只关心关键节点之间的异常传播。若两个关键节点本身可以直接联动,并且前者的时间戳严格小于后者,那么异常流量可以从前者传到后者。若两者时间戳相同,则它们之间不能建立传播方向。 一条传播链需要由若干个关键节点通过上述有向关系依次连接而成,因此它至少要包含一条有效链路。传播链的规模定义为链上所有节点的服务用户数 `Users` 之和。 请你帮助小红计算,在所有可能形成的传播链中,规模最大的那一条能覆盖多少用户。
输入描述:
第一行包含三个整数 `N`、`dist` 和 `Wthreshold`,分别表示基站数量、空间判定阈值和关键节点的负载门槛,其中 `1 接下来 `N` 行,每行给出五个整数 `x`、`y`、`t`、`w`、`Users`,表示一个基站的横坐标、纵坐标、时间戳、负载值和服务用户数。所有坐标、时间戳、负载值和用户数都在 `[0, 10^9]` 范围内。


输出描述:
输出一个整数,表示最大传播链能够覆盖的用户总数。 如果不存在关键节点,或者关键节点之间无法形成任何有效链路,则输出 `0`。
示例1

输入

4 1 5
0 0 1 3 4
0 1 2 2 6
0 2 3 3 8
5 5 4 10 100

输出

18

说明

前三个基站两两只会和相邻位置直接联动。它们各自所在邻域的负载和分别为 5、8、5,所以这三个点都是关键节点,并且能按时间顺序形成一条从第一个点到第三个点的连续传播链,覆盖用户数为 4+6+8=18。最后一个基站虽然自身也是关键节点,但它和其他点距离过远,无法参与任何有效链路。
加载中...