Toggle navigation
ZSTUOJ
常见问答
问题
来源/分类
状态
排名
竞赛&作业
Login
Language
中文
ئۇيغۇرچە
English
فارسی
ไทย
한국어
问题4273--玩具
4273: 玩具
[命题人 :
]
时间限制 :
1.000
sec
内存限制 :
128 MB
提交
题目描述
商店有
n
个玩具,第
i
个玩具有价格
a[i]
和快乐值
b[i]
。有一天,小王来到商店想买一些玩具,商店老板告诉他,如果他买的所有玩具的位置是连续的,那么老板答应小王购买的所有玩具中某一个可以免费。小王接受老板的提议,他现在有零花钱
k
可以用来买玩具,那么他能获得的最大的快乐值是多少。
输入
第一行给测试总数
T(T <= 100)
,接下来有
T
组测试数据。
每组测试数据第一行有两个数字
n(1 <= n <= 5000)
和
k(0 <= k <= 1000000000)
。
第二行有
n
个数字,第
i
个数字表示第
i
个玩具的价格
a[i](1 <= a[i] <= 1000000)
。
第三行有
n
个数字,第
i
个数字表示第
i
个玩具的快乐值
b[i](1 <= b[i] <= 1000000)
。
输出
每组测试输出小王能获得的最大快乐值。
样例输入
Copy
3 5 14 1 2 3 4 5 5 4 3 2 1 3 1 100 1000 10000 100 1000 10000 1 0 1000000 1000000
样例输出
Copy
15 10000 1000000
来源/分类