Es un día caliente de verano y Bessie la vaca tiene bastante pereza. Ella quiere ubicarse en una posición en su campo de tal manera que ella pueda alcanzar tanto pasto delicioso como sea posible dentro de únicamente una distancia corta.

Hay ~N~ parches de pasto en el campo de Bessie. El í-ésimo de tales parches contiene ~g_i~ unidades de pasto y está ubicando en un punto distinto ~(x_i, y_i)~ en el campo. A Bessie le gustaría elegir un punto en el campo como su posición inicial (posiblemente el mismo punto que un parche de pasto) de tal manera que una cantidad máxima de pasto esté dentro de una distancia de ~K~ pasos desde su ubicación.

Cuando Bessie toma un paso, ella se mueve 1 unidad al norte, sur, este u oeste de su posición actual. Por ejemplo, para moverse de ~(0, 0)~ a ~(3, 2)~ esto requiere 5 pasos en total.

Por favor, ayude a Bessie a determinar la cantidad máxima de pasto a la que ella puede alcanzar, si ella elije la mejor posición inicial posible.

Entrada

• Línea 1: Los enteros ~N~ y ~K~.
• Líneas 2..1+N: La línea i+1 describe el iésimo parche de pasto usando tres enteros: ~g_i, x_i, y_i~.

Salida

La cantidad máxima de pasto que Bessie puede alcanzar dentro de ~K~ pasos, si ella se ubica en la mejor posición inicial posible.

Restricciones

• ~1 \leq N \leq 100,000~
• ~1 \leq g_i \leq 10,000~
• ~0 \leq x_i, y_i \leq 1,000,000~
• ~1 \leq K \leq 2,000,000~

Ejemplo de Entrada

4 3
7 8 6
3 0 0
4 6 0
1 4 2

Detalles de la Entrada: Bessie desea desplazarse a lo más 3 pasos desde su posición inicial. Hay 4 parches de pasto. El primero contiene 7 unidades de pasto y está ubicado en la posición ~(8, 6)~ y así sucesivamente.

Ejemplo de Salida

8

Detalles de la Salida: Ubicándose en ~(3, 0)~, el pasto en las posiciones ~(0, 0), (6,0)~ y ~(4, 2)~ está dentro de ~K~ unidades de distancia.

USACO 2014 March Contest, Gold. Problem 1: The Lazy Cow.