La vaca perezosa
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 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 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 a 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 y .
Líneas 2..1+N: La línea i+1 describe el iésimo parche de pasto usando tres enteros: .
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 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 , el pasto en las posiciones y está dentro de unidades de distancia.
Comments