背景

他清楚地知道这一次醒来，将不会看见阳光里天使低头，似乎要亲吻他的嘴唇。

原本就剩着不多的夕阳彻底坠落下去，铺天盖地的黑暗开始侵袭这个房间。

那棵很大的、树叶都掉光了的梧桐树还在夜风中挥舞它的枝桠。

题目描述

有一个长度为 $n$ 的序列，第 $\forall i\in[1, n]$ 个位置上有权值 $p_i$ 和能量值 $a_i$。

一开始你的能量值，疲劳值和贡献值均为 $0$，可以从序列上的任意位置出发。

假定当前你位于第 $x$ 个位置，拥有 $t$ 的能量值，疲劳值为 $k$，那么可以获得 $\lfloor \frac{p_x}{2^k} \rfloor$ 的贡献值。

接着，你可以同时对自己的能量值和疲劳值分别进行操作： $t\leftarrow a_x$，$k\leftarrow 0$，也可以不操作。

然后，在 $x + t \le n$ 并且 $t \not= 0$ 的时候，你可以移动到 $x + t$ 的位置，并使得疲劳值 $k\leftarrow k + 1$，也可以不移动，然后结束所有操作。

请求出从某个点出发的最大贡献值之和。

输入格式

第一行一个整数 $n$，表示序列长度为 $n$。

接下来 $n$ 行，每行两个整数 $p_i, a_i$，分别表示每个位置上的权值和能量值。

输出格式

一行一个整数，表示最大的贡献值之和为多少。

3
2 2
2 1
3 1

3

9
1 3
4 2
5 3
1 2
2 2
3 3
4 2
2 2
5 1

8

8
1 1
7 1
1 1
5 2
1 1
3 3
6 1
1 2

11

提示

样例解释

样例一解释：

从第 $1$ 个位置出发的最大贡献值之和是：$p_1 + \lfloor \frac{p_{1 + a_1}}{2^1} \rfloor = 3$。

从第 $2$ 个位置出发的最大贡献值之和是：$p_2 + \lfloor \frac{p_{2 + a_2}}{2^1} \rfloor = 3$。

从第 $3$ 个位置出发的最大贡献值之和是：$p_3 = 3$。

故最大的贡献值是 $3$。

样例二解释：

一种可以使贡献值之和最大的方案是：$p_3 + \lfloor \frac{p_6}{2} \rfloor + \lfloor \frac{p_9}{2} \rfloor = 8$。

数据范围

本题采用捆绑测试。

• Subtask 1（5 pts）：保证 $\forall i\in[1, n], a_i = 1$。
• Subtask 2（15 pts）：保证 $\forall i\in[2, n], a_i = a_{i - 1}$。
• Subtask 3（10 pts）：$n\le 20$。
• Subtask 4（15 pts）：$n\le 500$。
• Subtask 5（20 pts）：$n\le 2000$。
• Subtask 6（20 pts）：$n\le 10^5$。
• Subtask 7（15 pts）：无特殊限制。

对于所有数据，$1\le n\le 5\times 10^5$，$1\le p_i\le 10^9$，$1\le a_i\le n$。