题目背景

某小区有若干栋别墅，按照编号规则排列：

• 中心别墅编号为 $1$
• 若某栋别墅编号为 $i$，则它左侧的别墅编号为 $2i$，右侧的别墅编号为 $2i+1$

每栋别墅都有一个安保价值。

安保公司规定：如果某栋别墅安排了巡逻，那么与之直接相邻的别墅（即编号与它满足 $i$ 和 $2i$、$i$ 和 $2i+1$ 关系的别墅）就不能再安排巡逻。

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

题目描述

给定 $n$ 栋别墅及其编号和安保价值，按上述相邻规则，选中一栋别墅后，与它直接相邻的别墅都不能被选中。求能选中的别墅价值之和的最大值。

输入格式

第一行一个整数 $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$），与 $1$ 相邻的 $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$。