2054:饭店排队

文件提交:无需freopen 内存限制:128 MB 时间限制:1.000 S
评测方式:普通裁判 命题人:
提交:2 解决:2

题目描述

有 $n$ 位顾客正在饭店门口排队等待吃饭,饭店只有一张桌子,一次只能容纳一位顾客吃饭。

队伍从前往后每位顾客的编号分别为 $1\to n$。店家统计了每位顾客吃饭需要的时间,第 $i$ 位顾客吃饭需要花费 $a_i$ 分钟,最多只会等待 $b_i$ 分钟。

每位顾客吃完饭后都会立马让下一位顾客开始吃饭,所以某位顾客的等待时间,就会是他前面所有进入了饭店吃饭的顾客的吃饭时间之和。如果这个时间超过了他的最多等待时间,他就不会进入饭店吃饭,而是在轮到他时直接离开。

目前桌子刚好清空,轮到 $1$ 号顾客进去吃饭了。 $2\to n$ 号顾客都开始等待。老板有一个特权,可以在 $2\to n$ 号顾客中选择一位顾客不接待,将他直接从队伍中去掉。老板希望让吃饭的顾客尽可能多,请计算去掉谁(或都不使用特权)可以让吃饭的顾客尽可能多,输出最多可以有多少位顾客进入饭店吃饭。

输入

第一行一个整数 $n$

第二行 $n$ 个整数 $a_1\to a_n$

第三行 $n$ 个整数 $b_1\to b_n$

$1\le n\le 5000,1\le a_i,b_i\le 10^5$

输出

输出一个整数,即最多可以有多少位顾客进入饭店吃饭

样例输入-1 复制

5
3 2 3 4 7
1 3 5 8 12

样例输出-1 复制

5

样例输入-2 复制

5
3 2 3 4 7
1 3 5 8 11

样例输出-2 复制

4

提示

样例解释:

样例一:五位顾客都能在自己等待时间的极限进入饭店吃饭,老板不需要使用特权。

样例二:轮到 $5$ 号顾客时,他已经等待了 $12$ 分钟,但是他最多只能容忍等待 $11$ 分钟,所以他没法进入饭店,只能有 $4$ 位顾客进入饭店。如果老板使用特权,也无法让这个人数变得更多。