luogu#P8109. [Cnoi2021] 幻想乡程序设计大赛

[Cnoi2021] 幻想乡程序设计大赛

题目背景

幻想乡,春。

新年的土地吐出稚嫩的幼芽,第一届幻想乡程序设计大赛(Inner-Gensokyo Programming Contest, IGPC)拉开帷幕。作为举办者, Cirno 却有些不得不考虑的事情。

那就是气球的分配问题。

题目描述

本场比赛共有 nn 道题,Cirno 已经精确预测了每道题目的 AC 队伍数 a1,a2,a3,,ana_1,a_2,a_3,\cdots,a_n。但由于经费限制,主办方 nn 种颜色的气球分别只准备了 b1,b2,b3,,bnb_1,b_2,b_3,\cdots,b_n 个。

而 Cirno 需要合理地安排每道题目对应的气球颜色,使得能派发的气球尽可能多。

显然地,每道题目只能对应一种颜色的气球,每种颜色的气球只能对应一道题目,如果一道题有队伍通过但该种颜色的气球已经发完了,则很遗憾,该队拿不到这种气球了。

由于这个问题过于 trival,于是 Cirno 决定将这个任务分配给你。

输入格式

第一行,一个整数 nn

第二行,nn 个整数,用空格隔开,表示 {an}\{a_n\}

第三行,nn 个整数,用空格隔开,表示 {bn}\{b_n\}

输出格式

一行,一个整数,表示最多能派发的气球数。

5
1 2 3 4 5
2 3 3 3 3
12

提示

数据范围与约定

对于 100%100\% 的数据保证 1n1051 \le n \le 10^50ai,bi1040 \le a_i,b_i \le 10^4,且 {an},{bn}\{a_n\},\{b_n\} 单调不降。

子任务

Subtask1(6060 points):n8n \le 8

Subtask2(4040 points):无特殊限制。