Longe de Casa

Na montanha do Peak, $n$ exploradores estão perdidos!

Pedro Gallo e seu fiel companheiro, o Bing Bong, planejam usar um helicóptero para resgatar os exploradores. Ele escolherá uma posição na montanha para pousar, e os exploradores terão que alcançar o helicóptero para serem resgatados.

O mapa da montanha pode ser representado por um plano cartesiano, sendo as posições representadas por pontos de coordenadas inteiras. Cada explorador está em uma posição inicial $(x, y)$, tem energia $k$ e possui uma unidade de foguete. Com $1$ de energia ele pode se mover uma unidade verticalmente ou horizontalmente, ou, ao utilizar seu foguete (ainda utilizando $1$ de energia), se mover quanto quiser na direção vertical ou horizontal. Mais formalmente, se a energia do explorador for positiva, ele pode gastar $1$ de energia para fazer uma das seguintes ações:

• Ir para $(x+1, y)$, $(x-1, y)$, $(x, y+1)$ ou $(x, y-1)$.
• Se o explorador ainda tiver seu foguete, ir para $(x+d, y)$ ou $(x, y+d)$ para qualquer inteiro $d$ (note que $d$ pode ser negativo). Ao realizar esta ação, o foguete se quebra e não pode mais ser utilizado.

Escolhida a posição do helicóptero, um explorador poderá ser resgatado somente se consegue se mover até ela, a partir de sua posição inicial, com as ações descritas. Ajude Pedro Gallo e Bing Bong e calcule a maior quantidade de exploradores que poderá ser salva ao escolher a posição de pouso de forma ótima.

Entrada

A primeira linha de entrada contém um inteiro $n$ $(1 \leq n \leq 2\cdot 10^5)$ — o número de exploradores.

A $i$-ésima das próximas $n$ linhas contém três inteiros $x_i, y_i, k_i$ $(1 \leq x_i, y_i, k_i \leq 2\cdot 10^5)$ — a posição inicial $(x_i, y_i)$ do $i$-ésimo explorador e sua energia $k_i$.

Saída

Imprima um único inteiro — a maior quantidade de exploradores que pode ser salva escolhendo a posição de pouso do helicóptero de forma ótima.

3
1 1 1
2 2 1
3 3 1

2

3
10 21 2
19 30 2
20 19 1

3

5
1 1 1
1 1 1
100 100 1
100 100 1
100 100 1

5

7
77090 53996 1
198356 90124 4
91506 118145 3
91595 112415 1
1718 180618 3
70396 46316 118358
85973 72452 6

3