解题获得的最高分数

题目描述

给你一个下标从 0 开始的二维整数数组 questions，其中 questions[i] = [pointsi, brainpoweri]。

这表示一场考试中的一系列题目，你需要按顺序（即从题目 0 开始依次考虑），对于每个题目选择 解决 或者 跳过：

• 如果你解决第 i 题：
  • 可以获得 pointsi 分；
  • 但是之后的 brainpoweri 个题目都不能解决（即从第 i+1 题到第 i+brainpoweri 题只能跳过）。
• 如果你跳过第 i 题，则可以继续对第 i+1 题自由选择解决或跳过。

请你返回这场考试中，你能够获得的最高总分。

---

输入格式

• 第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示题目数量；
• 接下来 $n$ 行，每行包含两个整数 pointsi 和 brainpoweri（$1 \leq \text{pointsi}, \text{brainpoweri} \leq 10^5$），表示第 $i$ 题的信息。

---

输出格式

输出一个整数，表示在最优策略下可以获得的最高分数。

---

示例

示例 1

输入：

4
3 2
4 3
4 4
2 5

输出：

5

解释：

一种最优方案是解第 0 题和第 3 题：

• 解第 0 题：得 3 分，之后的第 1、2 题不能再解；
• 跳过第 1、2 题；
• 解第 3 题：得 2 分。

总得分为 $3 + 2 = 5$，无法获得更高得分。

---

示例 2

输入：

5
1 1
2 2
3 3
4 4
5 5

输出：

7

解释：

一种最优方案是解第 1 题和第 4 题：

• 跳过第 0 题；
• 解第 1 题：得 2 分，之后的第 2、3 题不能再解；
• 跳过第 2、3 题；
• 解第 4 题：得 5 分。

总得分为 $2 + 5 = 7$，无法获得更高得分。

---

数据范围

• $1 \leq n \leq 10^5$
• $1 \leq \text{pointsi}, \text{brainpoweri} \leq 10^5$