시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 512 MB240351437423.187%

문제

정우는 생일을 맞아 친구들에게 기프티콘을 N개 선물받았다. 어떤 기프티콘을 언제 쓸지 다 계획을 정해놨는데, 멍청한 정우는 기프티콘에 기한이 있다는 사실을 까맣게 잊고 있었다. 다행히 기프티콘에는 기한 연장 기능이 있다. 한 기프티콘을 한 번 연장할 때마다 기한이 30일씩 늘어난다.

정우는 기프티콘의 기한 연장을 너무 귀찮아하기 때문에, 기한 연장을 최소한으로 하고 싶어한다. 그리고 정우는 강박증이 있어서, 남은 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용할 수 있다. 단, 기한이 가장 적게 남은 기프티콘이 여러 개라면 그 중 아무거나 선택할 수 있다. 하루에 여러 기프티콘을 사용하거나 연장하는 것 모두 가능하다.

최소 횟수로 기한 연장을 하면서 기프티콘을 다 쓸 수 있도록 정우를 도와주자.

입력

첫째 줄에 기프티콘의 수 N이 주어진다.

둘째 줄에 A1A2, ..., AN가 주어진다. 이는 i번째 기프티콘의 남은 기한이 Ai일이라는 뜻이다.

셋째 줄에 B1B2, ..., BN가 주어진다. 이는 i번째 기프티콘을 Bi일 뒤에 사용할 계획이라는 뜻이다.

출력

첫째 줄에 정우가 기한 연장을 해야 하는 최소 횟수를 출력한다.

정답이 32비트 정수를 넘을 수 있으므로 유의하라.

제한

  • 1 ≤ N ≤ 100,000
  • 1 ≤ Ai ≤ 1,000,000,000
  • 1 ≤ Bi ≤ 1,000,000,000

서브태스크 1 (40점)

이 서브태스크는 다음의 조건을 만족한다.

  • 1 ≤ N ≤ 1,000
  • 1 ≤ Ai ≤ 1,000 
  • 1 ≤ Bi​ ≤ 1,000 

서브태스크 2 (60점)

이 서브태스크는 추가 제한 조건이 없다.

예제 입력 1

3
10 5 4
10 100 30

예제 출력 1

5
  • 4일에 2, 3번 기프티콘 연장
  • 10일에 1번 기프티콘 사용
  • 30일에 3번 기프티콘 사용
  • 34일에 2번 기프티콘 3회 연장
  • 100일에 2번 기프티콘 사용

출처

High School > 선린인터넷고등학교 > 2019 선린 정보 알고리즘경시대회 B번

채점 및 기타 정보

  • 예제는 채점하지 않는다.