Тимофей устраивает соревнования по спортивному ориентированию в своём офисе. Схема офиса представлена в виде дерева. Посещая каждый пункт, можно зарабатывать или терять очки. Если в узле записано положительное число, это значение добавляется к текущему количеству очков участника. Если отрицательное —– очки вычитаются. Если 0 –— их количество не меняется.

Нужно определить, какое максимальное число очков можно заработать, пройдя по пути из какого-то пункта A в какой-то (возможно, тот же) пункт B.

Путь не обязательно должен проходить через корень или содержать лист. Путь должен содержать по крайней мере один узел.

Пример 1:
В дереве всего три вершины, во всех вершинах записаны положительные числа, поэтому объединим все три вершины в один путь. В ответе получим: 1+1+2 = 4.

Пример 2:
Теперь в дереве есть вершина с отрицательным весом, через неё в данном случае проходить будет невыгодно. Оптимальный путь: 2+7+3 = 12.

Пример 3:
Оптимальный путь: 7+2+3+9 = 21.

Пример 4:
В этот раз имеет смысл пройти через вершину с отрицательным весом, так как в левом поддереве вершины − 3 лежит 5. Оптимальный путь: 2 +2 − 3+5 = 6.

Требования к решению: передаваемое в качестве аргумента дерево нельзя менять. Не храните вспомогательную информацию в вершинах.

На вход подается корень дерева.

Замечания про отправку решений

По умолчанию выбран компилятор make. Решение нужно отправлять в виде файла с расширением, которое соответствует вашему языку программирования.

Go:

package main

/**
Comment it before submitting 
type Node struct {  
	value  int  
	left   *Node  
	right  *Node  
}
**/

func Solution(root *Node) int {
    // Your code
    // “ヽ(´▽｀)ノ”
}

Функция должна вернуть число, равное максимальному количеству очков, которое можно заработать, попав из города А в город В.