구현상의 불규칙성
시간 제한1초메모리 제한1024 MB
해결한 각 문제에 필요한 컴퓨터 시간과 대회 중 해당 문제를 해결한 시각이 주어질 때, 팀이 사용했을 수 있는 컴퓨터의 최소 대수를 구한다.
문제
최근 BAPC 예선에서 상위 팀들의 성적에 감명을 받은 당신은, 팀들이 문제를 구현할 때 컴퓨터를 한 대만 사용할 수 있는지 여러 대를 사용할 수 있는지 궁금해졌다.
조직에 불필요하게 질문을 더 하러 가지 않고, 당신은 이 문제를 직접 알아내기로 한다. 심사위원이므로, 당신은 각 문제를 푸는 데 필요한 컴퓨터 시간의 추정치를 이미 알고 있다.
이 정보와, 상위 팀이 푼 각 문제를 대회 중 몇 시각에 풀었는지를 이용하여, 그 팀이 사용한 컴퓨터 수의 최솟값을 구하라.
팀은 한 문제도 통과하기 전에 여러 문제를 동시에 작업할 수 있다. 또한, 참가자들은 멀티태스킹을 잘하여 한 문제를 여러 대의 컴퓨터로 동시에 작업할 수 있지만, 각 컴퓨터는 한 번에 한 문제에만 사용할 수 있다.
입력
입력은 다음과 같다.
- 정수 ()이 주어지는 한 줄. 은 대회의 문제 수이다.
- 개의 정수 ()이 주어지는 한 줄. 는 문제 를 푸는 데 필요한 컴퓨터 시간이다.
- 개의 정수 ( 또는 )이 주어지는 한 줄. 는 문제 를 푼 시각이며, 풀지 않았다면 이다.
팀이 적어도 한 문제는 풀었음이 보장된다.
출력
팀이 사용한 컴퓨터 수의 최솟값을 출력하라.