题目描述
小A有n个水果，n个水果排成一排，第i个水果的种类是ai，第i个水果的单价是wi
小A想要选一种水果卖出，但是小A只能卖出连续的一段种类相同的水果。
所以卖出之前，小A需要可以交换两个相邻的水果，这个操作可以执行任意次。但是执行一次需要花费c的代价。
请问小A进行一次卖水果，最多可以收获多少钱。

输入输出格式
输入格式：
第一行两个整数n,m,c，表示水果的个数以及种类，以及交换一次的代价。
第二行n个整数，第i个整数表示ai，表示第i个水果的种类。
第三行m个整数，第i个整数表示wi，表示第i种水果的单价。

输出格式：
一行一个整数，表述最大收益。

输入输出样例
输入样例#1： 
5 3 1
1 2 3 3 2 
4 3 1
输出样例#1：
4
补充说明
【数据范围】
对于 100% 的数据，1<=m<=n<=1000, 1<=ai<=m, 1<=wi,c<=1000.
时间限制：1s 空间限制：512M

Rt，仅求助算法，蒟蒻想不出来（貌似是图）