You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

房间分配

题目描述

某假日酒店有 $N$ 种级别的房间，编号从 $0 \sim N-1$ ，其中 $0$ 号是最高级别，编号越大级别越低，级别为 $i$ 的房间有 $x_i$ 间。该酒店最近开发了一款给住客预订房间的APP，住客可以在APP上预订他所需要的房间级别，到达酒店之后再根据酒店能分配到的房间入住。

住客会根据他们预订的房间级别和实际入住的房间级别来对酒店进行评价，如果住客预订的房间级别为 $s$ ，实际入住的房间级别为 $t$ ，那么会发生以下三种情况之一：

1. 如果 $t < s$，住客会感到高兴，并会为酒店点赞。
2. 如果 $t = s$，住客会感到满意，不会有任何反应。
3. 如果 $t > s$，住客会感到生气，并会给酒店差评。

在客流量很大的这一天，预订房间级别为 $s$ 的住客有 $y_s$ 人，酒店想知道应该怎么给所有住客分配房间，使得点赞数减去差评数最大。输出这个最大值。

输入格式

第一行包含一个整数 $N$，表示房间级别的数量。

第二行包含 $N$ 个整数 $x_0,x_1,\cdots,x_{N-1}$，表示不同级别房间数量。

第三行包含 $N$ 个整数 $y_0,y_1,\cdots,y_{N-1}$，表示预订不同级别的房间的住客的数量。

输出格式

输出一个整数，表示通过最佳分配得到的点赞数减去差评数的最大值。注意这个值可能是负数。

样例 #1

样例输入 #1

2
3 3
1 3

样例输出 #1

2

样例 #2

样例输入 #2

3
1 1 1
1 1 1

样例输出 #2

1

样例 #3

样例输入 #3

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

样例输出 #3

1

样例 #4

样例输入 #4

4
2 1 1 8
0 4 4 0

样例输出 #4

-1

样例 #5

样例输入 #5

1
1000000000
1000000000

样例输出 #5

0

提示

样例解释

样例1：预订级别 $0$ 的房间的用户分配到 $0$ 级房间，将两个预订级别 $1$ 的房间的用户分配到 $0$ 级房间（获得 2 次赞），并将剩余的预订级别 $1$ 的房间的用户分配到 $1$ 级房间。最终最大值为 $2$。

在第二个样例中，你可以将预订级别 $1$ 的房间的用户分配到 $0$ 级房间，将预订级别 $2$ 的房间的用户分配到 $1$ 级房间，并将级别 $0$ 的用户分配到 $2$ 级房间。这将导致 $2$ 次赞和 $1$ 次踩，最大值为 $1$。

数据范围

对于全部数据，$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$。

• 子任务一（$16$ 分）：$N=2$，$x_i\le 100$，$y_i\le 100$。
• 子任务二（$9$ 分）：对于任意 $(i,j)$，$x_i=x_j=y_i=y_j$。
• 子任务三（$19$ 分）：$x_i,y_i\le 1$。
• 子任务四（$24$ 分）：$N,x_i,y_i\le 100$。
• 子任务五（$32$ 分）：无特殊限制。