A. Vegetables
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are a farmer, and you want to grow a wide variety of vegetables so that the people in your town can eat a balanced diet.

In order to remain healthy, a person must eat a diet that contains $$$N$$$ essential vegetables, numbered from $$$1$$$ to $$$N$$$. In total, your town requires $$$A_i$$$ units of each vegetable $$$i$$$, for $$$1 \leq i \leq N$$$. In order to grow a single unit of vegetable $$$i$$$, you require $$$B_i$$$ units of water.

However, you can use upgrades to improve the efficiency of your farm. In a single upgrade, you can do one of the following two actions:

  1. You can improve the nutritional value of your produce so that your town requires one less unit of some vegetable $$$i$$$. Specifically, you can choose any one vegetable $$$i$$$ such that $$$A_i \geq 1$$$, and reduce $$$A_i$$$ by $$$1$$$.
  2. You can improve the quality of your soil so that growing one unit of some vegetable $$$i$$$ requires one less unit of water. Specifically, you can choose any one vegetable $$$i$$$ such that $$$B_i \geq 1$$$, and reduce $$$B_i$$$ by $$$1$$$.

You wish to answer $$$Q$$$ questions numbered from $$$1$$$ to $$$Q$$$, where the $$$j$$$-th question is the following:

  • If you use at most $$$X_j$$$ upgrades, what is the minimum possible number of units of water you will need to feed your town?
Input

The first line contains two space-separated integers $$$N$$$ and $$$Q$$$, the number of essential vegetables and the number of questions, respectively.

The second line contains $$$N$$$ space separated integers, $$$A_1$$$, $$$A_2$$$, $$$...$$$ $$$A_N$$$.

The third line contains $$$N$$$ space separated integers, $$$B_1$$$, $$$B_2$$$, $$$...$$$ $$$B_N$$$.

The following $$$Q$$$ lines describe the questions. The $$$j$$$-th of these lines contains a single integer $$$X_j$$$.

Output

You should print $$$Q$$$ lines of output. The $$$j$$$-th line should be the answer to the $$$j$$$-th question.

Scoring

The test data for this problem is divided into multiple subtasks. In order to pass a subtask, your submitted program must solve every test case within that subtask correctly and within the time and memory limits.

You will be awarded the points allocated to a subtask if at least one submission you make during the contest passes that subtask. You do not need to combine your solutions for multiple subtasks into a single submission.

Please keep in mind that the subtasks are not necessarily arranged in increasing order of difficulty. We encourage you to try as many subtasks as possible.

Constraints

In all test data, it is guaranteed that:

  • $$$1 \leq N \leq 2 \cdot 10^5$$$.
  • $$$1 \leq Q \leq 2 \cdot 10^5$$$.
  • $$$1 \leq A_i \leq 10^6$$$ for all $$$1 \leq i \leq N$$$.
  • $$$1 \leq B_i \leq 10^6$$$ for all $$$1 \leq i \leq N$$$.
  • $$$1 \leq X_j \leq 10^9$$$ for all $$$1 \leq j \leq Q$$$.

Please be aware that the output for this problem may not fit in 32-bit integers. You may need to use 64-bit integers in your computations.

Subtasks

  • Subtask 1 (7 points) $$$Q = 1$$$, $$$X_j = 1$$$, $$$N \leq 10$$$, $$$A_i \leq 10^3$$$, $$$B_i \leq 10^3$$$.
  • Subtask 2 (6 points) $$$Q \leq 3$$$, $$$X_j \leq 3$$$, $$$N \leq 10$$$.
  • Subtask 3 (9 points) $$$A_i = 1$$$, $$$N \leq 10^3$$$, $$$Q \leq 10^3$$$.
  • Subtask 4 (7 points) $$$A_i = 1$$$.
  • Subtask 5 (18 points) $$$N, Q, X_j \leq 30$$$.
  • Subtask 6 (15 points) $$$N, Q, X_j \leq 400$$$.
  • Subtask 7 (16 points) $$$N, Q \leq 10^3$$$.
  • Subtask 8 (7 points) The sum of all $$$A_i$$$ does not exceed $$$2 \cdot 10^5$$$. Also, the sum of all $$$B_i$$$ does not exceed $$$2 \cdot 10^5$$$.
  • Subtask 9 (7 points) $$$X_j \leq 2 \cdot 10^5$$$.
  • Subtask 10 (8 points) No additional constraints.
Examples
Input
4 2
2 4 5 3
5 2 3 3
1
2
Output
37
32
Input
4 1
1 4 2 3
5 4 3 6
29
Output
0
Input
14 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1
4 2 4 12 10 5 2 6 4 10 2 3 5 12
3
9
5
6
Output
47
13
31
26
Input
8 6
7 9 4 2 2 2 7 7
1 10 6 7 4 6 8 4
29
3
12
27
8
19
Output
8
209
125
20
159
72
Input
1 1
1000000
1000000
1
Output
999999000000
Note

In example 1, there are two operations.

  • For the first query, $$$X_1 = 1$$$ so you are allowed up to $$$1$$$ upgrade. One optimal choice is to reduce $$$A_1$$$ by $$$1$$$. Then, the final array $$$A$$$ is $$$[1, 4, 5, 3]$$$ and the final array $$$B$$$ is $$$[5, 2, 3, 3]$$$. This yields a water requirement of $$$37$$$ units.
  • For the second query, $$$X_2 = 2$$$ so you are allowed up to $$$2$$$ upgrades. One optimal choice is to reduce $$$A_1$$$ by $$$1$$$ and reduce $$$B_3$$$ by $$$1$$$. Then, the final array $$$A$$$ is $$$[1, 4, 5, 3]$$$ and the final array $$$B$$$ is $$$[5, 2, 2, 3]$$$. This yields a water requirement of $$$32$$$ units.

Example 1 is valid for subtasks 2, 5, 6, 7, 8, 9 and 10.

In example 2, there is only one operation. You are allowed up to $$$29$$$ upgrades, which is sufficient to make the final array $$$A$$$ and the final array $$$B$$$ both $$$[0, 0, 0, 0]$$$. This yields a water requirement of $$$0$$$ units.

Example 2 is valid for subtasks 5, 6, 7, 8, 9 and 10.

Example 3 is valid for subtasks 3, 4, 5, 6, 7, 8, 9 and 10.

Example 4 is valid for subtasks 5, 6, 7, 8, 9 and 10.

Example 5 is valid for subtasks 2, 5, 6, 7, 8, 9 and 10.