책장

찬수는 1번부터 N번까지 번호가 붙은 N권의 책을 가지고 있다. i번 책의 두께는 ti, 높이는 hi이다. 책은 반드시 번호가 증가하는 순서대로 책장에 꽂아야 하며, 순서를 바꿀 수 없다.

책은 책장의 가장 아래 칸부터 위 칸으로 차례대로 꽂는다. 같은 칸에서는 왼쪽부터 오른쪽으로 번호 순서대로 꽂는다. 한 번 위 칸으로 올라가 책을 꽂기 시작하면, 다시 아래 칸으로 내려가 책을 꽂을 수 없다.

한 칸의 높이는 그 칸에 꽂힌 책들 중 가장 높은 책의 높이로 정해진다. 책장이 사용하는 전체 높이 H는 책이 꽂힌 모든 칸의 높이의 합이다. 한 칸의 폭은 그 칸에 꽂힌 책들의 두께의 합이고, 책장의 폭 L은 모든 칸의 폭 중 최댓값이다. 책장을 이루는 나무의 두께는 고려하지 않는다.

모든 책을 꽂은 뒤 max(H, L)이 가능한 한 작아지도록 책장을 설계하려고 한다. 가능한 최소값을 구하시오.

첫째 줄에 책의 수 N이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐, 책 번호 순서대로 각 책의 두께 ti와 높이 hi가 공백으로 구분되어 주어진다.

모든 책을 꽂은 뒤 책장 전체 높이 H와 책장 폭 L 중 큰 값 max(H, L)의 최소값을 정수로 출력한다.

• 1 <= N <= 100,000
• 1 <= ti, hi <= 10,000