A94870.最佳球队组建

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

现有 nn 名球员,第 ii 名球员(1in1 \le i \le n)具有两个属性:分数 sis_i 和年龄 aia_i

教练希望从这 nn 名球员中选出一个子集组成一支球队,使得球队中所有球员的分数之和最大。但是,球队的选拔必须遵循无矛盾原则

对于球队中的任意两名球员 iijj,若他们的年龄不同,则年龄较小的球员的分数不得严格大于年龄较大的球员。即:
ai<aja_i < a_j,则必须满足 sisjs_i \le s_j

如果两名球员年龄相同(ai=aja_i = a_j),则他们之间不会产生矛盾。

请计算出在满足无矛盾原则的前提下,球队所能达到的最大分数之和

输入格式

输入共三行。
第一行包含一个正整数 nn,表示球员的数量。
第二行包含 nn 个正整数 s1,s2,,sns_1, s_2, \dots, s_n,表示每位球员的分数。
第三行包含 nn 个正整数 a1,a2,,ana_1, a_2, \dots, a_n,表示每位球员的年龄。

输出格式

输出一个整数,表示无矛盾球队的最大总得分。

输入输出样例

  • 输入#1

    5
    1 3 5 10 15
    1 2 3 4 5

    输出#1

    34
  • 输入#2

    4
    4 5 6 5
    2 1 2 1

    输出#2

    16
  • 输入#3

    4
    1 2 3 5
    8 9 10 1

    输出#3

    6

说明/提示

【样例解释 2】
最优方案是选择第 2、3、4 名球员(下标从 1 开始):

  • 球员 2:分数 5,年龄 1
  • 球员 3:分数 6,年龄 2
  • 球员 4:分数 5,年龄 1
    总分:5+6+5=165 + 6 + 5 = 16
    其中球员 2 和 4 年龄相同(均为 1),无冲突;球员 3 年龄为 2,且分数 6 大于年龄为 1 的球员分数,符合规则。

【数据范围】

对于 100%100\% 的数据,满足:

  • 1n10001 \le n \le 1000
  • 1si1061 \le s_i \le 10^6
  • 1ai10001 \le a_i \le 1000
首页