任务收益

题目描述

有 $n$ 项任务，第 $i$ 项任务需要占用 $1$ 个单位时间来完成，能带来 $p_i$ 的收益，并且必须在时刻 $d_i$ 之前（含时刻 $d_i$）完成。时间被分成编号为 $1, 2, 3, \dots$ 的单位时间片，任意两个任务不能占用同一个时间片。

请选择一部分任务并给它们安排时间片，使得总收益最大，输出这个最大的总收益。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $d_i$ 与 $p_i$，保证 $1 \le d_i \le n$。

输出格式

一行一个整数，表示最大总收益。

样例

输入样例

3
2 10
1 5
2 8

输出样例

18

样例解释

选择收益为 $10$ 与 $8$ 的两项任务，分别放在时刻 $1$ 和时刻 $2$，总收益 $18$，比「先选收益 $5$ 的任务」更好。

数据范围

$1 \le n \le 2 \times 10^5$，$1 \le d_i \le n$，$1 \le p_i \le 10^9$。