레이팅 미적용Impressed by the performance of the top teams at the recent BAPC preliminaries, you started to wonder whether teams were allowed to use one or multiple computers to implement their solutions.
Instead of unnecessarily bothering the organization with more questions, you will figure this out by yourself. Being a jury member, you already have estimates for the computer time required to solve each problem.
Using this information, and the time in the contest at which the top team solved each of their solved problems, compute the minimal number of computers used by the team.
The team may work on multiple problems before getting any one of them accepted. Furthermore, the contestants are great multitaskers and can work on a single problem using multiple computers at the same time, but each computer can only be used for one problem at a time.
The input consists of:
- One line containing an integer \(n\) (\(1\leq n\leq 10^5\)), the number of problems in the contest.
- One line containing \(n\) integers \(t_1, t_2, \dots, t_n\) (\(1\leq t_i \leq 10^4\)), the computer time required to solve problem \(i\).
- One line containing \(n\) integers \(s_1, s_2, \dots, s_n\) (\(1\leq s_i \leq 10^9\) or \(s_i = -1\)), the time at which problem \(i\) was solved, or \(-1\) if it was not solved.
It is guaranteed that the team solved at least one problem.
Output the minimum number of computers used by the team.
11
50 8 10 6 300 5 6 3 18 5 12
117 23 63 6 -1 48 80 42 37 13 131
1
1
10
3
4
2
2 4
3 3
2
2
4 6
10 10
1