题目描述

一个装有宝石的圆环上，按顺时针方向标有 \(1,2,…,L\) 共 \(L\) 个点，相邻两点之间的距离均为 \(1\) 厘米。在这 \(L\) 个点中有 \(n\) 个点处镶嵌有宝石，每个宝石均有一定的价值。现有一根彩带，它触碰到圆环上镶嵌着的连续的宝石，就可以把这些宝石取出来。编程计算，当彩带长度为 \(k\) 厘米时，怎样能取出最多价值的宝石。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为三个正整数 \(n(≤×10^5),L(≤10^8),k(≤10^8)\)；第二行有 \(n\) 个不超过 \(L\) 且互不相同的正整数，表示镶嵌有宝石的位置；第三行有 \(n\) 个正整数 \(v_i(≤10^4)\)，表示对应位置上的宝石的价值；所有数字以空格隔开。

输出格式

对于每组数据，输出能取出的宝石价值和的最大值。

样例1

样例输入1

2
3 11 2
9 5 11
4 6 5
3 11 5
9 5 11
4 6 5

样例输出1

9
11

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("gem.in","r",stdin);
freopen("gem.out","w",stdout);