← 返回题目列表

Codeforces · 1822/A

A. 管管饲料

中文机器翻译题面 查看原题

蘑菇菲利波夫给自己做了一顿饭,在吃午饭的时候,他决定在 TubeTube 上观看一段视频。他吃午餐的时间不能超过 $$$t$$$ 秒,因此他请求你帮助选择视频。

TubeTube 源是 $$$n$$$ 视频的列表,索引从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个视频持续 $$$a_i$$$ 秒,具有娱乐价值 $$$b_i$$$。最初,提要在第一个视频上打开,Mushroom 可以在 $$$1$$$ 秒内跳到下一个视频(如果下一个视频存在)。蘑菇可以跳过视频任意次数(包括零次)。

帮助蘑菇选择一个他可以在 $$$t$$$ 秒内打开并观看的视频。如果有几个,他想选择最有趣的一个。打印任何适当视频的索引,如果没有,则打印 $$$-1$$$。

输入

输入数据的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 1000$$$) — 测试中测试用例的数量。

测试用例的描述如下。

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$t$$$ ($$$1 \le n \le 50$$$, $$$1 \le t \le 200$$$) - 分别是 Feed 中的视频数量和午餐的秒数。

测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$) - 视频的持续时间。

测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le 100$$$) — 视频的娱乐价值。

输出

输出$$$q$$$个整数,每个整数都是对应测试用例的答案。作为答案,输出蘑菇将有时间观看的最有趣的视频的索引。如果有多个答案,您可以输出其中任何一个。输出$$$-1$$$,如果午休时间没有视频可以看。

示例

输入 #1

5
5 9
1 5 7 6 6
3 4 7 1 9
4 4
4 3 3 2
1 2 3 4
5 7
5 5 5 5 5
2 1 3 9 7
4 33
54 71 69 96
42 24 99 1
2 179
55 66
77 88

输出 #1

3
2
3
-1
2