Problem Background

Day 2 Problem B.

The problem statement is translated from EGOI2024 bikeparking. The translation was done by ChatGPT and manually proofread. If there are any errors, please contact rui_er.

Problem Description

Sanne recently came up with a profitable business idea: renting premium bicycle parking spaces at the Eindhoven train station. To maximize her profits, she divided the bicycle parking spaces into $N$ different levels, numbered from $0$ to $N - 1$. Level $0$ is the premium level, located very close to the train platform. The higher the level number, the worse the parking space. The number of parking spaces at level $t$ is $x_t$.

Users allocate their parking spaces through an application. Each user has a subscription level and expects to get a parking space at the corresponding level. However, the terms of service do not guarantee that users will get a parking space at their corresponding level.

If a user with subscription level $s$ is assigned a parking space at level $t$, one of the following three scenarios occurs:

1. If $t < s$, the user will be happy and will like the application.
2. If $t = s$, the user will be satisfied and will not react.
3. If $t > s$, the user will be angry and will give the application a bad review.

Today, Sanne's application has $y_0 + y_1 + \cdots + y_{N-1}$ users, where $y_s$ is the number of users with subscription level $s$. She needs your help to allocate users to parking spaces. Each user should get one parking space. A parking space cannot be assigned to multiple users, but some parking spaces can remain unassigned. Additionally, the total number of users does not exceed the total number of available parking spaces.

Sanne wants to maximize her application's rating. Let $U$ be the number of likes and $D$ be the number of dislikes. Your task is to maximize $U - D$ by optimally allocating users to parking spaces.

Input Format

The first line contains an integer $N$, representing the number of levels or subscription levels.

The second line contains $N$ integers $x_0, x_1, \cdots, x_{N-1}$, representing the number of parking spaces at different levels.

The third line contains $N$ integers $y_0, y_1, \cdots, y_{N-1}$, representing the number of users at each subscription level.

Output Format

Output a single integer, representing the maximum possible value of $U - D$ that can be achieved by optimally allocating users to parking spaces.

Sample Input and Output

Sample Input #1

2
3 3
1 3

Sample Output #1

2

Sample Input #2

3
1 1 1
1 1 1

Sample Output #2

1

Sample Input #3

6
1 0 1 1 0 1
1 1 0 0 1 0

Sample Output #3

1

Sample Input #4

4
2 1 1 8
0 4 4 0

Sample Output #4

-1

Sample Input #5

1
1000000000
1000000000

Sample Output #5

0

Notes

Sample Explanation

In the first sample, you can assign the user with subscription level $0$ to a level $0$ parking space, assign two users with subscription level $1$ to level $0$ parking spaces (getting 2 likes), and assign the remaining user with subscription level $1$ to a level $1$ parking space. This results in a score of $2$.

In the second sample, you can assign the user with level $1$ to a level $0$ parking space, assign the user with level $2$ to a level $1$ parking space, and assign the user with level $0$ to a level $2$ parking space. This will result in 2 likes and 1 dislike, giving a score of $1$.

In the third sample, you can assign the user with level $1$ to a level $0$ parking space, assign the user with level $0$ to a level $2$ parking space, and assign the user with level $4$ to a level $3$ parking space. This will again result in 2 likes and 1 dislike, giving a score of $1$.

In the fourth sample, as shown in the diagram below, you can assign the users with level $1$ to level $0, 0, 3, 3$ parking spaces, resulting in 2 likes and 2 dislikes. Next, assign the users with level $2$ to level $1, 2, 3, 3$ parking spaces, resulting in 1 like and 2 dislikes. This equates to 3 likes and 4 dislikes, giving a score of $-1$.

In the fifth sample, you can assign each user to a parking space matching their own subscription level, so the score is $0$.

Data Range

For all data, $1 \le N \le 3 \times 10^5$, $0 \le x_i, y_i \le 10^9$, $y_0 + y_1 + \cdots + y_{N-1} \le x_0 + x_1 + \cdots + x_{N-1} \le 10^9$.

• Subtask 1 (16 points): $N = 2$, $x_i \le 100$, $y_i \le 100$.
• Subtask 2 (9 points): For any $(i, j)$, $x_i = x_j = y_i = y_j$.
• Subtask 3 (19 points): $x_i, y_i \le 1$.
• Subtask 4 (24 points): $N, x_i, y_i \le 100$.
• Subtask 5 (32 points): No special restrictions.

Note: Some test cases are included in multiple subtasks during EGOI. To save evaluation resources and streamline data organization, these test cases are placed in the subtask with the smallest number that includes them. This may result in a code receiving a higher score than expected, but it will not allow the code to pass the problem.

见题面 Input 部分

见题面 Output 部分