题目描述

忙忙碌碌镇有一条环岛公路，按顺时针方向有 \(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\)