问题 6638 --偏偏希望无价

6638: 偏偏希望无价

时间限制: 2 Sec  内存限制: 256 MB
提交: 3  解决: 2
[提交][状态][命题人:]

题目描述

「慈玉女士,要不是您一直送来物资和善款,福利院恐怕……」
她轻轻抚摸着孩子们的头,制止了院长的话头。
「只要我在,不用担心以后的日子…至于这些话,也不必说给孩子们听,增添他们的忧虑。」
孩子们仰起头,叽叽喳喳与她谈着最近的趣事,烦恼和梦想。
「慈玉女士,下次来是什么时候?」
「平时工作不要太累了哦,要早点睡觉……」
「慈玉女士,长大了我一定要成为和你一样的人!」
她望着孩子们清澈的双眼,突然愣了一下。
「和我一样的人……」
孩子将苹果递给她,「嗯!给别人带来光和希望的人!」
贫乏、过失、忧愁、苦难…她行走在银河之间,收取他人的抵押,给予等价的回报。
生命因欲望而存在,因欲望而奔走,因欲望而死去——这是无可抵抗的规律,亦是生命的必然。
表里不一的慈善家,抵押灵魂的恶商…她被世人赋予诸般身份,也只有她自己才明白这些举止背后的道义。

慈玉典押正在接待一名新的顾客。
顾客是一名股票投机商,他需要在 n 天内买入尽可能多的某公司的股票。
第 i 天的股票每股售价为 a[i] 元,每天只能最多购买一股。
投机商的可用资金在每天结束时会增加 m 元(即当天增加的可用资金,到第二天才能使用),可累计,初始科用资金为 0 ,任何时候投机商的可用资金都不能为负数。
求 n 天后,投机商最多可以买到多少股股票。

输入

第一行输入一个整数 T (1≤T≤10^4) ,表示数据组数。
每组数据第一行包含两个整数 n,m (1≤n≤2·10^5, 1≤m≤10^3) ,表示天数和每天资金增加数。
每组数据第二行 n 个整数 a[1],a[2],...,a[n] (1≤a[i]≤1000),表示每天的股票每股售价。
保证所有 n 之和不超过 2·10^5 。

输出

对于每组数据输出一行包含一个整数,表示求 n 天后,投机商最多可以买到多少股股票。
样例输入
Copy
6
3 3
2 2 2
6 5
2 2 8 2 6 8
6 4
4 10 3 8 6 10
2 1
1 1
4 1
4 1 3 1
4 2
1 3 4 3
样例输出
Copy
2
4
3
1
2
1

提示

来源

[提交][状态]