Maximizing App Rating through Optimal Parking Allocation

Sanne has devised a profitable business idea: renting out premium bike parking spaces at Eindhoven train station. She has divided the parking spaces into \(N\) levels, numbered from \(0\) to \(N-1\). Level \(0\) is the premium level, located closest to the platform, and as the level number increases, the quality of parking deteriorates. The number of spots available at level \(t\) is \(x_t\).

The app assigns a parking spot to each user. There are \(y_0 + y_1 + \cdots + y_{N-1}\) users in total, where \(y_s\) is the number of users with subscription level \(s\). Each user expects a spot at the level corresponding to their subscription. However, the service does not guarantee that users will get a spot at exactly their subscription level.

If a user with subscription \(s\) is assigned a parking space at level \(t\), one of three things happens:

1. If \(t < s\), the user is delighted and gives a +1 like (a bonus vote).
2. If \(t = s\), the user is neutral.
3. If \(t > s\), the user is upset and leaves a -1 dislike (a penalty vote).

Sanne wants to maximize her app's overall score, defined as \(U - D\) (the number of likes minus the number of dislikes), by optimally assigning parking spaces to users. Each user must be assigned exactly one parking space, each parking space can be assigned to at most one user, and it is allowed for some parking spaces to remain unused. It is guaranteed that the total number of users does not exceed the total number of parking spaces.

Goal: Determine the maximum possible value of \(U - D\) under an optimal assignment.

Note: In our formulation, assigning a user with subscription \(s\) to level \(t\) yields a score of:

[ \text{score}(s,t)=\begin{cases} +1, & \text{if } t < s,\ 0, & \text{if } t = s,\ -1, & \text{if } t > s.\ \end{cases} ]

inputFormat

The input is given as follows:

N
x0 x1 ... x(N-1)
y0 y1 ... y(N-1)

where N is the number of parking levels, the second line contains \(N\) integers \(x_0, x_1, \dots, x_{N-1}\) representing the available spots at each level, and the third line contains \(N\) integers \(y_0, y_1, \dots, y_{N-1}\) representing the number of users with the corresponding subscription levels.

outputFormat

Output a single integer: the maximum possible value of \(U - D\) if the parking spaces are assigned optimally.

sample

3
2 2 2
1 1 1

2