FIICode 2025 Qualifying Round - Studenți | Golderberg

Task

Joe Golderberg is a very quiet guy from Galați. He spends most of his time reading books and working as a bookseller. He also enjoys restoring books and has a special room in the basement of the bookstore for this craft. He visits this room on different days, and when he does, he can choose to put one or more books in for restoration, take one or more books out, or do nothing.

Joe received $k$ books from his friend, Loaf. Each book $i$ ($1 \le j \le k$) has an optimal restoration time $t_j$, which represents the ideal number of days it should stay in the special room.

Additionally, each book has a maximum selling price $c_j$, which is obtained if the book spends exactly $t_j$ days in the restoration room.

The selling price of a book is calculated using the formula: $max(0, c_j - |b - (a + t_j)|)$, where:

• $a$ is the day the book was placed in restoration,
• $b$ is the day the book was taken out.

Note: Joe must put all books up for restoration. Additionally, he can enter the restoration room multiple times on the same day, meaning he can leave a book in on $z_i$ and pick it up on the same day $z_i$, but in this case, it will count as $0$ full days of restoration.

Joe wants to buy a bouquet of flowers for Loaf and needs to maximize his profit from selling the $k$ books.

Input data

The first line of input contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) - the number of days in which Joe visits the restoration room.
The second line of input contains $n$ integers $z_1,z_2,\ldots,z_n$ ($1 \le z_1 < z_2 < \ldots < z_n \le 10^9$) - the days in which Joe visits the restoration room.
The third line of input contains a single integer $k$ ($1 \le k \le 3 \cdot 10^5$; $n \cdot k \le 3 \cdot 10^5$) - the number of books.
The fourth line of input contains $k$ integers $t_1,t_2,\ldots,t_k$ ($1 \le t_i \le 10^9$) - the optimal times that the books need to spend in the restoration room.
The fourth line of input contains $k$ integers $c_1,c_2,\ldots,c_k$ ($1 \le c_i \le 10^9$) - the maximum selling prices of the books after restoration.

It is guaranteed that $n \cdot k \le 3 \cdot 10^5$.

Output data

Print one integer, the maximum profit you can achieve after restoring all $k$ books.

Example

stdin

2  
5 14  
3  
10 7 1  
3 13 14 

stdout

26

Explanation

We have $n = 2$ available days: $5$ and $14$.
We have $k = 3$ books, each with their respective restoration times and optimal costs.

Book $1$: If placed on day $5$, it should ideally be taken out on day $15$, but there is no day $15$ available. The closest is $14$, meaning a penalty of $|14 - (5 + 10)| = 1$. So its selling price is $max(0, 3 - 1) = 2$.

Book $2$: If placed on day $5$, it should ideally be taken out on day $12$, but we only have day $14$, meaning a penalty of $|14 - (5 + 7)| = 2$. Selling price $= max(0, 13 - 2) = 11$.

Book $3$: If placed on day $5$ and removed the same day, it gets $0$ full days of restoration. Since $t_3 = 1$, the penalty is $|5 - (5 + 1)| = 1$, so its selling price $= max(0, 14 - 1) = 13$.

Total Profit $= 2 + 11 + 13 = 26$.