题目描述

忙忙碌碌镇有一条环岛公路，按顺时针方向有 $1、2、…、t$ 共 $t$ 个城市，相邻两城市之间的距离均为 $1$ 公里。在这 $t$ 个城市中有 $n$ 个城市里拥有一定价值的天然气。现有镇长想修一条高铁连接某些城市，高铁进入的城市就可以得到该城市所有的天然气。请你计算，当高铁长度为 $k$ 公里时，怎样能取出最多价值的天然气。

格式

输入格式

第 $1$ 行为三个正整数 $n≤100000,t≤100000000,k≤100000$；

第 $2$ 行有 $n$ 个不超过 $t$ 的正整数，表示有天然气城市位置；第 $3$ 行有 $n$ 个正整数 $v_i≤10000$，表示对应城市里天然气的价值；所有数字以空格隔开。

输出格式

只有一个正整数，表示能取出的天然气价值和的最大值。

样例1

样例输入1

3 11 2
9 5 11
4 6 5

样例输出1

9

来源

地址：$\text{Online~Judge}$
作者：征宇
模拟赛$T3$