시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB205525.000%

문제

In a quest to be the very best, you have decided to set out on your journey around the region to prove your strength by collecting gym badges. You begin your solo adventure with your first and only Pokemon, which happens to be a legendary Wabbit.

Your Wabbit starts at level $0$ and can only gain levels by challenging gyms. There are $N$ gyms numbered from $1$ to $N$ spread across the region and you can challenge them in any order. To prevent over grinding, gym $i$ has its own level cap $L_i$ where you can only challenge the gym if Wabbit’s current level is less than or equal to $L_i$.

As there may be different number of trainers to defeat in a gym, the number of levels that Wabbit gains after challenging a gym may differ. To be precise, Wabbit will gain $X_i$ levels after challenging gym $i$.

Each gym $i$ rewards successful challengers with their own unique gym badge $i$. Find the maximum number of unique gym badges that you can obtain if you challenge the gyms in an optimal way.

입력

Your program must read from standard input.

The first line contains an integer $N$, the number of gyms.

The second line contains $N$ integers, where the $i$th integer represents the level Wabbit gains by challenging $i$th gym, $X_i$.

The third line contains $N$ integers, where the $i$th integer represents the level cap of the $i$th gym, $L_i$.

출력

Your program must print to standard output.

The output should contain a single integer on a single line, the maximum number of unique gyms badges that can be won.

제한

  • $1 ≤ N ≤ 500\,000$
  • $1 ≤ X_i , L_i ≤ 10^9$

서브태스크

번호배점제한
115

$1 ≤ N ≤ 10$

29

$L_i$ is constant

327

$1 ≤ N ≤ 5000$

449

-

예제 입력 1

5
4 6 3 5 2
10 6 4 8 12

예제 출력 1

4

An optimal solution can be obatined when the gyms are challenged in the following order: $3$, $4$, $1$, $5$.

This testcase is valid for subtasks 1, 2 and 4.

예제 입력 2

5
3 9 4 2 6
10 10 10 10 10

예제 출력 2

4

An optimal solution can be obatined when the gyms are challenged in the following order: $1$, $3$, $4$, $2$.

Note that after the challenging gym $4$, Wabbit is at level $9$ which is within the level cap of gym $2$ and can thus challenge it.

At the end Wabbit will be at level $18$ which is above the level cap of the gym $5$ and hence cannot challenge it.

채점 및 기타 정보

  • 예제는 채점하지 않는다.