def bestCoordinate(towers, radius):
    # 暴力枚举
    dp = [[0] * 110 for _ in range(110)]
    x, y, power = 0, 0, 0
    for dx, dy, dpo in towers:
        for i in range(max(0, dx - radius), dx + radius + 1):
            for j in range(max(0, dy - radius), dy + radius + 1):
                d = math.sqrt((dx - i) ** 2 + (dy - j) ** 2)
                if d > radius:
                    continue
                cur = math.floor(dpo / (1 + d))
                dp[i][j] += cur
                if dp[i][j] > power:
                    x, y = i, j
                    power = dp[i][j]
                elif dp[i][j] == power and (i < x or (i == x and j < y)):
                    x, y = i, j
    return [x, y]

def arrayStringsAreEqual(word1, word2):
    j, c_j, cur2, w2_num = 0, 0, word2[0], len(word2)
    for i in range(len(word1)):
        for c in word1[i]:
            if c_j >= len(cur2):
                j += 1
                if j >= w2_num:
                    return False
                cur2 = word2[j]
                c_j = 0
            # print(c, cur2[c_j])
            if c != cur2[c_j]:
                return False
            c_j += 1
    if j + 1 < w2_num or c_j < len(cur2):
        return False
    return True

def magicalString(n):
    s = "122"
    if n <= 3:
        return 1
    ret, i, add = 1, 2, "1"
    while i < n:
        if s[i] == "1":
            ret += 1
        s += add * int(s[i])
        add = "1" if add == "2" else "2"
        i += 1
    return ret

def letterCasePermutation(s):
    # 回溯
    ret, cur = [], []
    def fun(i):
        if i >= s_num:
            ret.append("".join(cur))
            return
        if s[i].isdigit():
            cur.append(s[i])
            fun(i + 1)
            cur.pop()
        elif 65 <= ord(s[i]) <= 90: # 大写字母
            cur.append(s[i])
            fun(i + 1)
            cur.pop()
            cur.append(chr(ord(s[i]) + 32))
            fun(i + 1)
            cur.pop()
        else:                       # 小写字母
            cur.append(s[i])
            fun(i + 1)
            cur.pop()
            cur.append(chr(ord(s[i]) - 32))
            fun(i + 1)
            cur.pop()
    s_num = len(s)
    fun(0)
    return ret

def countMatches(items, ruleKey, ruleValue):
    ret = 0
    keys = {"type": 0, "color": 1, "name": 2}
    for item in items:
        if item[keys[ruleKey]] == ruleValue:
            ret += 1
    return ret

def topKFrequent(nums, k):
    def heap_up(i):
        cur, parent = i, (i - 1) >> 1
        while cur > 0 and heap[cur][1] >= heap[parent][1]:
            heap[cur], heap[parent] = heap[parent], heap[cur]
            heap_down(cur)
            cur = parent
            parent = (cur - 1) >> 1
        
    def heap_down(i):
        cur, left, right = i, 2 * i + 1, 2 * i + 2
        while left < heap_num :
            x, nex = heap[cur][1], cur
            if left < heap_num and x < heap[left][1]:
                nex = left
                x = heap[left][1]
            if right < heap_num and x < heap[right][1]:
                nex = right
            if cur != nex:
                heap[cur], heap[nex] = heap[nex], heap[cur]
                cur = nex
                left, right = 2 * cur + 1, 2 * cur + 2
            else:
                break
            

    # 堆排序
    heap = []
    heap_num = 0
    for num in nums:
        i = 0
        while i < heap_num and heap[i][0] != num: i += 1
        if i >= heap_num: 
            heap.append([num, 1])
            heap_num += 1
        else:
            heap[i][1] += 1
            # 上浮堆元素
            heap_up(i)
    # print(heap)
    # 输出结果
    ret = []
    for i in range(k):
        ret.append(heap[0][0])
        heap[0], heap[-1] = heap[-1], heap[0]
        heap.pop()
        heap_num -= 1
        heap_down(0)
        # print(ret[-1], heap)
    # print(ret)
    return ret

def sumSubarrayMins(arr):
    # 单调栈贡献法
    n = len(arr)
    left, right= [-1] * n, [n] * n
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            right[stack.pop()] = i
        stack.append(i)
    stack = []
    for i in range(n - 1 ,-1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            left[stack.pop()] = i
        stack.append(i)
    ret = 0
    for i in range(n):
        ret += (i - left[i]) * (right[i] - i) * arr[i]
    return ret % (10 ** 9 + 7)

def countBits(n):
    def count(x):
        if x == 0: return 0
        count_ = 0
        while x > 0:
            x &= (x - 1)
            count_ += 1
        return count_
    ret = []
    for i in range(n + 1):
        ret.append(count(i)) 
    return ret

def arraySign(nums):
    count = 0
    for num in nums:
        if num < 0:
            count += 1
        elif num == 0:
            return 0
    return 1 if count % 2 == 0 else -1

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    # 后序遍历
    """
    0: 代表没偷
    1: 代表偷了
    """
    def fun(node):
        if not node: return 0, 0
        l_pre_dp0, l_pre_dp1 = fun(node.left)
        r_pre_dp0, r_pre_dp1 = fun(node.right)
        dp0 = max(l_pre_dp0, l_pre_dp1) + max(r_pre_dp0, r_pre_dp1)
        dp1 = node.val + l_pre_dp0 + r_pre_dp0
        return dp0, dp1
    
    return max(fun(root))