← 返回题目列表

Codeforces · 2052/J

J. 明智的观察

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

吉尔喜欢在大学取得好成绩,因此她从不错过家庭作业的最后期限。但更重要的是,她喜欢观看该剧并与她最好的朋友约翰尼讨论。不幸的是,今天她需要在这两项活动中做出选择!

Jill 需要完成 $$$n$$$ 家庭作业。第 $$$i$$$ 任务需要 $$$a_i$$$ 分钟才能完成,从现在起最多需要 $$$d_i$$$ 分钟提交给教师。此外,约翰尼和吉尔还想讨论该系列的 $$$m$$$ 新剧集。第 $$$j$$$ 集持续 $$$l_j$$$ 分钟。吉尔可以按任何顺序完成任务,但她需要按剧集出现的顺序观看剧集。完成作业或观看剧集开始后都不能中断。

约翰尼和吉尔需要就 $$$t_k$$$ 打电话讨论该系列剧的时间达成一致。他们还不确定选择哪个时间。对于每个可能的时间,计算吉尔在该时间之前可以观看的最大集数,同时仍然能够及时完成所有 $$$n$$$ 家庭作业任务。

请注意,出于解决此问题的目的,我们假设在 $$$t_k$$$ 时间与 Johnny 讨论该系列剧不会占用 Jill 的大量时间,并且 即使她正在完成任何家庭作业, 也可能发生.

输入

输入中有多个测试用例。输入以测试用例的数量 $$$T$$$ ($$$1 \le T \le 1\,000$$$) 开始。

每个测试用例都以一行三个整数开头 $$$n$$$ ($$$1 \le n \le 200\,000$$$) - 作业任务数,$$$m$$$ ($$$1 \le m \le 200\,000$$$) - 集数,以及 $$$q$$$ ($$$1 \le q \le 200\,000$$$) — 与 Jill 通话的可能次数。

第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — 完成任务所需的分钟数。下一行包含 $$$n$$$ 整数 $$$d_i$$$ ($$$1 \le d_i \le 10^{15}$$$) - 必须完成此任务的截止日期。下一行包含 $$$m$$$ 整数 $$$l_j$$$ ($$$1 \le l_j \le 10^9$$$) - 按需要观看的顺序排列的剧集长度。下一行包含 $$$q$$$ 整数 $$$t_k$$$ ($$$1 \le t_k \le 10^{15}$$$) - 与 Jill 通话的可能次数。

可以在各自的期限内完成所有任务。

输入中所有测试用例的 $$$n$$$、$$$m$$$、$$$q$$$ 的总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,输出一行包含 $$$q$$$ 整数 - 对于每个可能的时间 $$$t_k$$$ ,吉尔可以观看的最大剧集数。

示例

输入
复制

2
1 2 3
10
15
5 5
5 15 20
3 4 5
8 100 8
10 150 20
2 32 1 1
9 200 51 50 10

输出
复制

1 1 2
1 4 2 2 1