만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

체육관 배지

면접 대비

시간 제한1.5초메모리 제한1024 MB

요약
각 체육관의 레벨 상승량 X_i와 레벨 상한 L_i가 주어질 때, 도전 전 레벨이 L_i 이하이도록 이길 수 있는 체육관 수의 최댓값을 구합니다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 힙
정답자
아직 제출이 없습니다

문제

가장 강해지겠다는 목표로 지역을 돌며 체육관 배지를 모으는 여행을 떠났습니다. 여행은 전설의 Wabbit 한 마리와 단둘이 시작합니다.

Wabbit의 시작 레벨은 00이고, 레벨은 체육관에 도전해야만 올라갑니다. 지역에는 11번부터 NN번까지 번호가 붙은 NN개의 체육관이 있으며, 원하는 순서로 도전할 수 있습니다. 레벨을 무리하게 올리지 못하도록 체육관 ii마다 레벨 상한 LiL_i가 있습니다. Wabbit의 현재 레벨이 LiL_i 이하일 때만 그 체육관에 도전할 수 있습니다.

체육관마다 상대하는 트레이너 수가 달라서, 도전 후 오르는 레벨도 체육관마다 다릅니다. 체육관 ii에 도전하면 Wabbit의 레벨이 XiX_i만큼 오릅니다. 체육관 ii를 이기면 고유한 배지 ii를 받습니다. 최적의 순서로 도전했을 때 얻을 수 있는 배지 개수의 최댓값을 구하세요.

입력

첫째 줄에 체육관의 개수 NN이 주어집니다. 둘째 줄에는 NN개의 정수가 주어집니다. ii번째 정수는 체육관 ii에 도전했을 때 Wabbit이 얻는 레벨 XiX_i입니다. 셋째 줄에는 NN개의 정수가 주어집니다. ii번째 정수는 체육관 ii의 레벨 상한 LiL_i입니다.

출력

얻을 수 있는 배지 개수의 최댓값을 한 줄에 정수 하나로 출력합니다.

제한

1≤N≤5000001 \le N \le 500000 1≤Xi,Li≤1091 \le X_i, L_i \le 10^9

예제2

  1. 예제 1

    입력
    5
    4 6 3 5 2
    10 6 4 8 12
    
    예상 출력
    4
    
  2. 예제 2

    입력
    5
    3 9 4 2 6
    10 10 10 10 10
    
    예상 출력
    4