A8523.排列

普及-

官方

通过率:0%

题目描述

出题人:小张张五

小星得到了一个 nn 的排列,记为数组 aa,现在他想把这个数组排序,小星每次可以依次进行下面的操作:

  • 选择数组两个位置。
  • 交换这两个位置上的数。

小星最多做 kk 次这样的操作,现在小星想要让这个数组的整齐度尽量高,请输出这个整齐度。

每个位置都有一个整齐度,数组的整齐度为其中位置编号(起点编号为 11)和在他上面的数相等的位置的整齐度之和,即

i=1n[ai=i]vi\sum_{i=1}^{n}[a_i=i]v_i

一个排列是 11nn 所有整数以任意顺序组成的长度为 nn 的数组,且每个数有且仅有出现一次。

输入格式

第一行包含一个正整数 nn 和一个整数 kk,代表数组长度,和可操作的次数。
第二行包含 nn 个正整数,a1,a2,...,ana_1,a_2,...,a_n,保证给出的是一个排列。
第三行包含 nn 个正整数,v1,v2,...,vnv_1,v_2,...,v_n,代表每个位置的整齐度。

输出格式

TT 行,每行一个整数,代表最大的整齐度。

输入输出样例

  • 输入#1

    5 2
    2 1 4 5 3
    1 1 1 1 2

    输出#1

    4

说明/提示

数据范围

对于 100%100\% 的数据,1ain1×1051\leq a_i\leq n\leq1\times10^50k2000\leq k\leq2001vi1×1091\leq v_i\leq1\times10^9

测试点编号 nn\leq kk\leq viv_i\leq
121\sim 2 55 55 1×1091\times10^9
343\sim 4 1×1051\times10^5 22 1×1091\times10^9
565\sim 6 1×1051\times10^5 200200 11
7107\sim 10 1×1051\times10^5 200200 1×1091\times10^9
首页