Background

「若你困于无风之地，

我将奏响高天之歌。」

如风般自由的吟游诗人，驻于牧歌之城。

--------------------------------------------------------------------

「我现在会为你歌颂美好的万物万象——

四季轮转，四风从不止息。

当然啦，功劳也不是它们的，主要是我的。

                           ——当温迪彻底沉醉于美酒时，他会如此放声歌唱。

Description

为了争夺蒙德第一吟游诗人的名号，六指乔瑟决定向温迪发起挑战。

具体来说，一张未完成的乐谱被定义为一个长度为 的音符序列 。而完成这张乐谱需要将它划分成恰好 个乐章，每个乐章的响度被定义为其中所有音符的权值之和。众所周知，蒙德的风是宁静祥和的，所以温迪认为一张完成的乐谱的动听度可以被其中响度最大的乐章刻画，且该最大响度越小则乐谱演奏出来越好听。

六指乔瑟自然不能任由温迪演奏出好听的乐曲，于是他们约定，六指乔瑟可以在温迪完成初始乐谱 之前对其做一些变换，以得到需要温迪完成的乐谱 。具体来说，存在一个长度为 的置换 ，六指乔瑟可以对 做不超过 次置换得到 ，即 。

温迪和六指乔瑟都是绝顶聪明的吟游诗人，在比赛完成之前你想知道最终演奏出来的乐谱的动听度是多少。

第一行三个正整数 。

第二行  个整数描述初始序列 。

第三行  个正整数描述置换 。

一个整数表示答案。

8 1 6
0 -7 8 -1 -3 9 -8 5
4 7 2 8 3 6 5 1

3

9 6 9
-1 -7 -10 -1 -5 5 8 -10 9
7 4 1 2 8 6 5 3 9

7

保证 



- 温迪想最小化最大响度，六指乔瑟想最大化最大响度。
- 若  是一个排列， 是一个置换，且满足 ，则有 。 不是一个排列，但可以看作是对它的下表排列做这个置换。