Сегодня жаркий летний день, и корова Беси чувствует себя утомлённой. Она хочет так расположиться на поле, чтобы она находилась на коротком расстоянии от как можно большего количества вкусной травы.
Имеется N участков с травой (1 <= N <= 100,000) на поле Беси. i-ый из этих участков содержит gi единиц травы (1 <= gi <= 10,000) и расположен в различных точках (xi, yi) поля (0 <= xi, yi <=1,000,000). Беси хочет выбрать точку для своего начального расположения так, что бы максимальное количество травы было достижимо не более чем за K шагов от этого положения (1 <= K <= 2,000,000).
Шаг Беси – это перемещение на 1 единицу к северу, югу, востоку или западу от текущей позиции. Например, перемещение из точки (0,0) в точку (3,2) требует 5 шагов.
Пожалуйста, помогите Беси определить максимальное количество травы, Которое она сможет достичь, если выберет наилучшее начальное расположение.
PROBLEM NAME: lazy
Формат входных данных
* Строка 1: Целые числа N и K.
* Строки 2..1+N: Строка i+1 опсиывает i-ый участок травы используя 3 целых числа: gi, xi, yi.
Формат выходных данных
* Строка 1: Максимальное количество травы, которое может достичь Беси за K шагов, если он выберет наилучшее начальное положение.
Примечание
Расположившись в точке (3,0) Беси обеспечит себе доступ к траве в позициях (0,0), (6,0), и (4,2) – все на расстоянии не превышающем K.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
7 8 6
3 0 0
4 6 0
1 4 2
|
8
|