Background

Day 2 Problem B.

This statement is translated from EGOI2024 bikeparking. The translation comes from ChatGPT and has been manually proofread. If there are mistakes, please contact rui_er.

Problem Description

Sanne recently came up with a profitable business idea: renting out premium bike parking spots at Eindhoven train station. To maximize her profit, she divides the bike parking spots into $N$ different levels, numbered from $0$ to $N - 1$. Level $0$ is the premium level and is very close to the platforms. Higher-numbered levels have worse parking spots. The number of parking spots at level $t$ is $x_t$.

Users are assigned their parking spots via an app. Each user has a subscription level and expects to get a parking spot at the corresponding level. However, the terms of service do not guarantee that users will get a spot at their corresponding level.

If a user with subscription level $s$ is assigned to a parking spot at level $t$, then one of the following three cases happens:

1. If $t < s$, the user is happy and will like the app.
2. If $t = s$, the user is satisfied and will not react.
3. If $t > s$, the user is angry and will dislike the app.

Today, Sanne's app 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 assign users to parking spots. Each user must get a parking spot. A parking spot cannot be assigned to multiple users, but some parking spots may be left unassigned. Also, the total number of users does not exceed the total number of available parking spots.

Sanne wants to maximize her app rating. Let $U$ be the number of likes and $D$ be the number of dislikes. Your task is to maximize $U - D$ by assigning users to parking spots in the best possible way.

Input Format

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

The second line contains $N$ integers $x_0,x_1,\cdots,x_{N-1}$, the number of parking spots at each level.

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

Output Format

Output one integer, the maximum possible value of $U - D$ that can be achieved by an optimal assignment of users to parking spots.

2
3 3
1 3

2

3
1 1 1
1 1 1

1

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

1

4
2 1 1 8
0 4 4 0

-1

1
1000000000
1000000000

0

Hint

Sample Explanation

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

In the second sample, you can assign the level $1$ user to a level $0$ parking spot, assign the level $2$ user to a level $1$ parking spot, and assign the level $0$ user to a level $2$ parking spot. This results in 2 likes and 1 dislike, for a rating of $1$.

In the third sample, you can assign the level $1$ user to a level $0$ parking spot, assign the level $0$ user to a level $2$ parking spot, and assign the level $4$ user to a level $3$ parking spot. This again results in 2 likes and 1 dislike, for a rating of $1$.

The fourth sample is shown in the figure below. You can assign level $1$ users to level $0, 0, 3, 3$ parking spots, resulting in 2 likes and 2 dislikes. Next, assign level $2$ users to level $1, 2, 3, 3$ parking spots, resulting in 1 like and 2 dislikes. This totals 3 likes and 4 dislikes, for a rating of $-1$.

In the fifth sample, you can assign everyone to a parking spot matching their own subscription level, so the rating is $0$.

Constraints

For all testdata, $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 additional constraints.

Note: Some test points in EGOI were placed into multiple subtasks. To save judging resources and reduce the workload of organizing the data, these test points were placed in the subtask with the smallest index among all subtasks that contain them. This may cause a solution to get a higher score than expected, but still fail to pass the problem.

Translated by ChatGPT 5