A79610.小明的餐馆开业
入门
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
由于你帮助小明开发了美味的菜品,小明决定在小镇上开一个餐馆。
小明决定直接从镇上已有的餐馆中收购其中一个店面作为自己的餐馆店面。小镇上目前有 n 个餐馆,其中第 i 个餐馆坐落于坐标 (xi,yi) 处,并且有客流量 zi 。
我们定义一个餐馆所在位置的繁华度为曼哈顿距离在 D 以内的所有餐馆的客流量总和(包括当前餐馆本身的客流量),请你帮助小明选择最繁华的位置用于开设餐馆,并且告诉他最大的繁华值是多少。
输入格式
第一行输入两个个整数 n(1≤n≤1000) ,代表小镇上的餐馆总数和决定繁华值额度的距离 D(0≤D≤1000)。
接下来 n 行每行给出 3 个整数 xi,yi,zi ,分别代表当前参观的坐标位置在 (xi,yi) ,且客流量为 zi。 (1≤xi,yi,zi≤1000)
输出格式
输出一个整数, 代表经过选择后餐馆的最大繁华值。
输入输出样例
输入#1
5 2 2 5 6 5 2 1 7 9 7 2 5 5 2 4 7
输出#1
18
说明/提示
曼哈顿距离即为两点横坐标距离的差值 + 纵坐标距离的差值。
即: a 点到 b 点的曼哈段距离 d(a,b)=∣(xa−xb)∣+∣(ya−yb)∣。