#P11328. [NOISG 2022 Finals] Gym Badges

    ID: 10810 Type: RemoteJudge 1500ms 500MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2022NOISG(新加坡)

[NOISG 2022 Finals] Gym Badges

题目描述

你是一只初始等级为 00Wabbit\text{Wabbit}。你希望到 nn 个比赛中提升自己的实力,并收集这些比赛的徽章。

目前将要举行的比赛共有 NN 个。第 ii 个比赛可以用 LiL_iXiX_i 来描述。如果你的当前等级 Li\le L_i,那么你可以参加第 ii 个比赛,让自己的等级提升 XiX_i 并获得一个徽章。

你可以以任意顺序参加这些比赛。求出如果按照最佳顺序参加,你最多可以获得多少个徽章。

输入格式

第一行,一个正整数 NN

第二行 NN 个整数,表示 XiX_i

第三行 NN 个整数,表示 LiL_i

输出格式

一行一个整数,表示最多能收集到的徽章个数。

5
4 6 3 5 2
10 6 4 8 12

4
5
3 9 4 2 6
10 10 10 10 10
4

提示

【样例 #1 解释】

一种最优的参加方式为 34153 \to 4 \to 1 \to 5

【样例 #2 解释】

一种最优的参加方式为 13421 \to 3 \to 4 \to 2

【数据范围】

Subtask\text{Subtask} 分值 特殊性质
00 样例
11 1515 1N101\le N\le10
22 99 所有 LiL_i 均相等
33 2727 1N50001\le N\le5000
44 4949

对于 100%100\% 的数据,$1 \le N \le 5 \times 10 ^ 5, 1 \le X_i, L_i \le 10 ^ 9$。