Problem I
Implementation Irregularities

Scoreboard of the BAPC 2021 preliminaries

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.

Sample Input 1 Sample Output 1
50 8 10 6 300 5 6 3 18 5 12
117 23 63 6 -1 48 80 42 37 13 131
Sample Input 2 Sample Output 2
Sample Input 3 Sample Output 3
2 4
3 3
Sample Input 4 Sample Output 4
4 6
10 10

Please log in to submit a solution to this problem

Log in