체육관 배지
면접 대비시간 제한1.5초메모리 제한1024 MB
각 체육관의 레벨 상승량 X_i와 레벨 상한 L_i가 주어질 때, 도전 전 레벨이 L_i 이하이도록 이길 수 있는 체육관 수의 최댓값을 구합니다.
문제
가장 강해지겠다는 목표로 지역을 돌며 체육관 배지를 모으는 여행을 떠났습니다. 여행은 전설의 Wabbit 한 마리와 단둘이 시작합니다.
Wabbit의 시작 레벨은 이고, 레벨은 체육관에 도전해야만 올라갑니다. 지역에는 번부터 번까지 번호가 붙은 개의 체육관이 있으며, 원하는 순서로 도전할 수 있습니다. 레벨을 무리하게 올리지 못하도록 체육관 마다 레벨 상한 가 있습니다. Wabbit의 현재 레벨이 이하일 때만 그 체육관에 도전할 수 있습니다.
체육관마다 상대하는 트레이너 수가 달라서, 도전 후 오르는 레벨도 체육관마다 다릅니다. 체육관 에 도전하면 Wabbit의 레벨이 만큼 오릅니다. 체육관 를 이기면 고유한 배지 를 받습니다. 최적의 순서로 도전했을 때 얻을 수 있는 배지 개수의 최댓값을 구하세요.
입력
첫째 줄에 체육관의 개수 이 주어집니다. 둘째 줄에는 개의 정수가 주어집니다. 번째 정수는 체육관 에 도전했을 때 Wabbit이 얻는 레벨 입니다. 셋째 줄에는 개의 정수가 주어집니다. 번째 정수는 체육관 의 레벨 상한 입니다.
출력
얻을 수 있는 배지 개수의 최댓값을 한 줄에 정수 하나로 출력합니다.
제한