‹ 上一题 下一题 ›

s09184. 退货窗口 未做

1000 ms 256 MB 测试点 10 通过率 33% S-06·贪心进阶与反悔贪心反悔贪心

题目描述

售后站收到 张退货单。站点按时段办事:时段 依次进行,每个时段恰好能办结一张退货单,同一时段不能办两张。第 张退货单若被安排在第 个时段或更早办结,站点获得报酬 ;放弃办理则分文不收。

每张退货单至多被安排一个时段。求站点能拿到的总报酬最大值。

输入格式

第一行一个整数 。

接下来 行,第 行两个整数 。

输出格式

一行一个整数:总报酬的最大值。

样例 1

样例

输入
5
1 9
2 5
2 6
3 7
3 2
输出
22

办第 张:依次排在时段 ,均不晚于各自截止,总报酬 。存在总报酬更大的选法吗?四个及以上的选法中总有一张要排在时段 之后,均不可行。

样例 2

办第 张:时段 办(截止 ),时段 办(截止 ),总报酬 ;第 张与第 张争抢时段 ,放弃报酬低的。

数据范围

;;。总报酬可能超过 位整数范围。

输入
输出

            
答案