题目背景

Day 2 Problem B.

题面译自 EGOI2024 bikeparking。翻译来自于 ChatGPT 并进行人工校对，若有误请联系 rui_er。

题目描述

Sanne 最近想出了一个有利可图的商业点子：在埃因霍温火车站出租高级自行车停车位。为了最大化她的利润，她将自行车停车位分成了 $N$ 个不同的级别，编号从 $0$ 到 $N - 1$。级别 $0$ 是高级级别，位置非常靠近火车站台。编号越高的级别停车位越差。级别 $t$ 的停车位数量为 $x_t$。

用户通过一个应用程序来分配他们的停车位。每个用户都有一个订阅等级，并期望在相应的级别获得一个停车位。然而，服务条款并不保证用户在他们的相应级别获得一个停车位。

如果订阅等级为 $s$ 的用户被分配到级别 $t$ 的停车位，那么会发生以下三种情况之一：

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

今天，Sanne 的应用有 $y_0 + y_1 + \cdots + y_{N-1}$ 名用户，其中 $y_s$ 是订阅等级为 $s$ 的用户数量。她需要你的帮助来将用户分配到停车位。每个用户应该得到一个停车位。不能将一个停车位分配给多个用户，但可以有一些停车位不分配给任何用户。此外，用户总数不超过可用停车位总数。

Sanne 希望最大化她的应用评分。设 $U$ 为点赞数，$D$ 为差评数。你的任务是通过最佳分配用户到停车位来最大化 $U - D$。

输入格式

第一行包含一个整数 $N$，表示级别或订阅等级的数量。

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

第三行包含 $N$ 个整数 $y_0,y_1,\cdots,y_{N-1}$，表示每个订阅等级的用户数量。

输出格式

输出一个整数，表示通过最佳分配用户到停车位所能得到的最大可能值 $U - D$。

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

提示

样例解释

在第一个样例中，你可以将订阅级别为 $0$ 的用户分配到 $0$ 级停车位，将两个级别为 $1$ 的用户分配到 $0$ 级停车位（获得 2 次赞），并将剩余的级别为 $1$ 的用户分配到 $1$ 级停车位。这导致评分为 $2$。

在第二个样例中，你可以将级别 $1$ 的用户分配到 $0$ 级停车位，将级别 $2$ 的用户分配到 $1$ 级停车位，并将级别 $0$ 的用户分配到 $2$ 级停车位。这将导致 2 次赞和 1 次踩，评分为 $1$。

在第三个样例中，你可以将级别 $1$ 的用户分配到 $0$ 级停车位，将级别 $0$ 的用户分配到 $2$ 级停车位，并将级别 $4$ 的用户分配到 $3$ 级停车位。这将再次导致 2 次赞和 1 次踩，评分为 $1$。

第四个样例如下图所示。你可以将级别 $1$ 的用户分配到 $0, 0, 3, 3$ 级停车位，导致 2 次赞和 2 次踩。接下来，将级别 $2$ 的用户分配到 $1, 2, 3, 3$ 级停车位，导致 1 次赞和 2 次踩。这相当于 3 次赞和 4 次踩，评分为 $-1$。

在第五个样例中，你可以将每个人分配到匹配其自身订阅级别的停车位，因此评分为 $0$。

---

数据范围

对于全部数据，$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$ 分）：无特殊限制。

注：部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量，这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数，但是无法过题。