Gym Badges

Interview

Time limit1.5sMemory limit1024 MB

Summary

Given each gym's level gain X_i and level cap L_i, find the most gyms you can challenge when your level must be at most L_i before each fight.

Level: Medium6 of 10
Topics: Greedy, Sorting, Heap
Solved: No attempts yet

Problem

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$ . You can only challenge the gym if Wabbit's current level is less than or equal to $L_i$ .

Each gym has a different number of trainers, so the number of levels Wabbit gains after a challenge differs by gym. Wabbit gains $X_i$ levels after challenging gym $i$ . Each gym $i$ rewards successful challengers with its own unique gym badge $i$ . Find the maximum number of unique gym badges you can obtain if you challenge the gyms in an optimal way.

Input

The first line contains an integer $N$ , the number of gyms. The second line contains $N$ integers, where the $i$ -th integer is $X_i$ , the level Wabbit gains by challenging gym $i$ . The third line contains $N$ integers, where the $i$ -th integer is $L_i$ , the level cap of gym $i$ .

Output

Print a single integer on one line, the maximum number of unique gym badges that can be won.

Constraints

$1 \le N \le 500000$ $1 \le X_i, L_i \le 10^9$

Examples2

Example 1
Input
```
5
4 6 3 5 2
10 6 4 8 12
```
Expected output
```
4
```
Example 2
Input
```
5
3 9 4 2 6
10 10 10 10 10
```
Expected output
```
4
```