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 ~(1 \leq N \leq 100,000)~ en el campo de Bessie. El íésimo de tales parches contiene g_i unidades de pasto ~(1 \leq g_i \leq 10,000)~ y está ubicando en un punto distinto ~(x_i, y_i)~ en el campo ~(0 \leq x_i, y_i \leq 1,000,000)~. 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 ~(1 \leq K \leq 2,000,000)~.

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~.

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.

Salida

• Línea 1: 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.

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.