题目背景

某小区有若干栋别墅，呈二叉树排列。每栋别墅有一个安保价值（表示其内部资产总值）。

安保公司制定巡逻计划时规定：如果某栋别墅安排了巡逻，那么它相邻的别墅（父节点和子节点）就不能再安排巡逻，以避免资源冲突。

物业公司想知道，在不违反规定的前提下，最多能保护的总资产价值是多少。

题目描述

给定一棵按堆式编号的二叉树：

• 根节点编号为 $1$
• 若节点编号为 $i$，则左子节点编号为 $2i$，右子节点为 $2i+1$
• 不一定所有编号都存在

选中一个节点后，它的父节点和子节点都不能被选中。求能选中的节点价值之和的最大值。

输入格式

第一行一个整数 $n$，表示节点个数。

接下来 $n$ 行，每行两个整数 $id, val$，表示节点编号和价值。保证 $val > 0$。

输出格式

输出一个整数，表示最大总价值。

样例输入

5
1 3
2 2
3 3
5 4
7 1

样例输出

8

样例解释

二叉树结构：

      1(3)
     / \
   2(2) 3(3)
     \    \
     5(4)  7(1)

方案一：选 $1$（$3$），$2,3$ 不能选，但孙子 $5,7$ 可以选 → $3+4+1=8$ 方案二：选 $2$ 和 $3$（$2+3=5$），$1,5,7$ 不能选 → $5$ 方案三：选 $5$（$4$）和 $2$（$2$），$1,3,7$ 不能选 → $6$

最优方案：选 $1,5,7$，总价值 $8$。

数据范围

$1 \le n \le 1000$，$1 \le id \le 2000$，$1 \le val \le 10000$。