Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Добро пожаловать в шоу «TV Time» мистера Ант Тенны! В этом раунде игры вам даны $n$ вёдер, где $i$-е ведро имеет максимальную вместимость $v_i$ единиц объёма воды. В начале игры все вёдра полностью наполняются водой, и ваша задача — сохранить как можно больше воды в течение следующих $t$ секунд. Но вот в чём подвох: эти вёдра дырявые! У $i$-го ведра скорость протечки равна $l_i$, что означает, что каждую секунду после начала игры из $i$-го ведра вытекает $l_i$ единиц объёма воды.

До начала игры вы можете объединить любое количество вёдер в одно. Получившееся ведро будет иметь вместимость, равную максимальной вместимости среди объединённых вёдер, и скорость протечки, равную минимальной скорости протечки среди объединённых вёдер. Вы можете выполнять объединения произвольное число раз, но все они должны быть выполнены до наполнения вёдер водой.

Тенна задаёт $q$ вопросов, где $i$-й вопрос имеет ограничение по времени $t_i$. Для каждого $1 \le i \le q$ вычислите максимальный суммарный сохранённый объём воды через $t_i$ секунд. Обратите внимание, что все вопросы независимы.

Входные данные

Входные данные состоят из нескольких наборов входных данных. Первая строка содержит целое число $T$ ($1 \le T \le 5 \times 10^4$) — количество наборов входных данных. Для каждого набора входных данных:

Первая строка содержит целое число $n$ ($1 \le n \le 2 \times 10^5$) — количество вёдер.

Вторая строка содержит $n$ целых чисел $v_1, v_2, \cdots, v_n$ ($1 \le v_i \le 4 \times 10^{13}$), где $v_i$ — вместимость $i$-го ведра.

Третья строка содержит $n$ целых чисел $l_1, l_2, \cdots, l_n$ ($0 \le l_i \le 10^9$), где $l_i$ — скорость протечки $i$-го ведра.

Четвёртая строка содержит целое число $q$ ($1 \le q \le 2 \times 10^5$) — количество вопросов.

Пятая строка содержит $q$ целых чисел $t_1, t_2, \cdots, t_q$ ($0 \le t_i \le 10^9$), где $t_i$ — ограничение по времени для $i$-го запроса.

Гарантируется, что ни сумма $n$, ни сумма $q$ по всем наборам входных данных не превысит $2 \times 10^5$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую $q$ целых чисел, разделённых пробелом, где $i$-е число — максимальный суммарный сохранённый объём воды через $t_i$ секунд.

Примеры

2
4
5 4 7 6
2 1 3 2
3
3 1 2
4
19 47 21 13
5 14 2 3
5
5 2 6 1 4
4 14 8
43 67 38 77 48

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.