题目描述
售后站收到 张退货单。站点按时段办事:时段 依次进行,每个时段恰好能办结一张退货单,同一时段不能办两张。第 张退货单若被安排在第 个时段或更早办结,站点获得报酬 ;放弃办理则分文不收。
每张退货单至多被安排一个时段。求站点能拿到的总报酬最大值。
输入格式
第一行一个整数 。
接下来 行,第 行两个整数 。
输出格式
一行一个整数:总报酬的最大值。
样例 1
样例
输入
5 1 9 2 5 2 6 3 7 3 2
输出
22
办第 张:依次排在时段 ,均不晚于各自截止,总报酬 。存在总报酬更大的选法吗?四个及以上的选法中总有一张要排在时段 之后,均不可行。
样例 2
输入
3 1 4 1 6 2 100
输出
106
办第 张:时段 办(截止 ),时段 办(截止 ),总报酬 ;第 张与第 张争抢时段 ,放弃报酬低的。
数据范围
;;。总报酬可能超过 位整数范围。