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.