seoulin1234   1년 전

문제

사람을 조심히 태우는 기관은 Line Town의 유명한 라인 버스를 관리합니다. 라인 버스는 1번부터 n번까지 번호가 매겨진 정류장을 순서대로 지나갑니다.
정류장 i에서,

  • 먼저 aᵢ명이 버스에서 내리고,

  • 그 다음 bᵢ명이 버스에 탑니다.

버스는 1번 정류장에서 비어있는 상태로 시작하며, 정류장을 번호 순서대로 지나갑니다. 마지막인 n번 정류장에서 모든 승객이 하차하여 버스가 완전히 비어야 합니다.

라인 버스를 이용하는 승객들은 모두 반드시 자리에 앉아야 합니다. 버스의 수용 인원은 c명이면 정확히 c개의 좌석이 있는 것으로 간주합니다. 운전자는 좌석 수에 포함되지 않습니다.

사람을 조심히 태우는 기관은 라인 버스를 운행하기 위해 필요한 **최소 버스 좌석 수(최소 수용 인원)**를 알고 싶어합니다.

입력

  • 첫 번째 줄에 정수 n이 주어집니다.
    (2 ≤ n ≤ 2 × 10⁵)

  • 그 다음 n줄에 걸쳐 각각 정수 aᵢ, bᵢ가 주어집니다.
    (0 ≤ aᵢ, bᵢ ≤ 10⁹)

추가 조건:

  • 적어도 한 명 이상은 반드시 버스에 탑니다.

  • 전체 정류장을 통틀어 버스에 탄 사람 수의 합은 최대 10⁹명 이하입니다.

  • n번 정류장에서 버스는 반드시 빈 상태가 되어야 합니다.

출력

  • 필요한 최소 버스 좌석 수를 하나의 정수로 출력하세요.

댓글을 작성하려면 로그인해야 합니다.