You want to transport artifacts through the Nile. The artifacts are numbered from to . The weight of artifact () is .

To transport the artifacts, you use specialized boats.
Each boat can carry **at most two** artifacts.

- If you decide to put a single artifact in a boat, the artifact weight can be arbitrary.
- If you want to put two artifacts in the same boat, you have to make sure the boat is balanced evenly. Specifically, you can send artifacts and () in the same boat only if the absolute difference between their weights is at most , that is .

To transport an artifact, you have to pay a cost that depends on the number of artifacts carried in the same boat. The cost of transporting artifact () is:

- , if you put the artifact in its own boat, or
- , if you put it in a boat together with some other artifact.

Note that in the latter case, you have to pay for both artifacts in the boat. Specifically, if you decide to send artifacts and () in the same boat, you need to pay .

Sending an artifact in a boat by itself is always more expensive than sending it with some other artifact sharing the boat with it, so for all such that .

Unfortunately, the river is very unpredictable and the value of changes often. Your task is to answer questions numbered from to . The questions are described by an array of length . The answer to question () is the minimum total cost of transporting all artifacts, when the value of is equal to .

#### Implementation Details

You should implement the following procedure.

```
std::vector<long long> calculate_costs(
std::vector<int> W, std::vector<int> A,
std::vector<int> B, std::vector<int> E)
```

- , , : arrays of integers of length , describing the weights of the artifacts and the costs of transporting them.
- : an array of integers of length describing the value of for each question.
- This procedure should return an array of integers containing the minimum total cost of transporting the artifacts, where gives the cost when the value of is (for each such that ).
- This procedure is called exactly once for each test case.

#### Constraints

- for each such that
- for each such that
- for each such that

#### Subtasks

Subtask | Score | Additional Constraints |
---|---|---|

1 | ; ; for each such that | |

2 | ; for each such that | |

3 | ; and for each such that | |

4 | ; | |

5 | ||

6 | and for each such that | |

7 | No additional constraints. |

#### Example

Consider the following call.

```
calculate_costs([15, 12, 2, 10, 21],
[5, 4, 5, 6, 3],
[1, 2, 2, 3, 2],
[5, 9, 1])
```

In this example we have artifacts and questions.

In the first question, . You can send artifacts and in one boat (since ) and the remaining artifacts in separate boats. This yields the minimum cost of transporting all the artifacts, which is .

In the second question, . You can send artifacts and in one boat (since ) and send artifacts and in one boat (since ). The remaining artifact can be sent in a separate boat. This yields the minimum cost of transporting all the artifacts, which is .

In the final question, . You need to send each artifact in its own boat. This yields the minimum cost of transporting all the artifacts, which is .

Hence, this procedure should return .

#### Sample Grader

Input format:

```
N
W[0] A[0] B[0]
W[1] A[1] B[1]
...
W[N-1] A[N-1] B[N-1]
Q
E[0]
E[1]
...
E[Q-1]
```

Output format:

```
R[0]
R[1]
...
R[S-1]
```

Here, is the length of the array returned by `calculate_costs`

.

#### Attachment Package

The sample grader along with sample test cases are available here.

## Comments