Las casas de un barrio forman un árbol binario y cada nodo guarda un monto. Un ladrón no puede entrar a dos casas unidas directamente por una arista (padre e hijo). Encuentra el mayor monto que puede juntar.

Entrada

El árbol viene en el formato de LeetCode, en dos líneas: la primera tiene un entero \(k\) y la segunda \(k\) elementos separados por espacios, que son el recorrido por niveles del árbol. Cada elemento es el valor de un nodo o null si ese hijo no existe; los hijos de un null no se escriben y los null del final se omiten. Un árbol vacío se escribe con \(k = 0\) y una línea vacía. El árbol tiene entre \(1\) y \(10^4\) nodos, con valores entre \(0\) y \(10^4\).

Salida

El mayor monto.

Ejemplo 1

Entrada

5
3 2 3 null 3 null 1

Salida

6

Ejemplo 2

Entrada

6
3 4 5 1 3 null 1

Salida

9

Ejemplo 3

Entrada

1
5

Salida

5