스케줄링 최적화 회사인 SOPT 에 완료해야 할 개의 작업 t1, t2, … , tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti 를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나를 선택할 수 있다. 작업 ti 를 완료하기 위해 머신 A를 선택하면 ai 시간이 걸리고 머신 B를 선택하면 bi 시간이 걸린다. 각 머신은 어느 순간에 최대 하나의 작업만 수행할 수 있으며, 한 작업이 시작되면 그 작업을 완료하기 전까지 다른 작업을 그 머신에서 수행할 수 없다. SOPT 는 모든 작업을 완료하기 위한 최소의 완료 시간을 구하고자 한다.

예를 들어, 세 개의 작업이 t1, t2, t3가 주어져 있고 a1 = 2, b1 = 3, a2 = 5, b2 = 3, a3 = 2, b3 = 7라고 하자. 완료 시간을 최소화하기 위해서는 작업 t1, t3는 머신 A에, 작업 t2는 머신 B에 할당한다. 머신 A는 작업 t1, t3를 완료하는데 2 + 2 = 4 시간이 걸리고 머신 B는 작업 t2를 완료하는데 3 시간이 걸린다. 따라서 최소 완료 시간은 4 시간이 된다.

n개의 작업 t1, t2, … , tn 과 각 머신에서 각 작업들을 수행하는 데 걸리는 시간들이 주어질 때, 모든 작업들을 완료하기 위해 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.​ 

입력은 표준입력을 사용한다. 첫 번째 줄에 작업의 개수를 나타내는 양의 정수 n (1 ≤ n ≤ 250)이 주어진다.

다음 개의 줄에서 번째 줄에는 두 개의 정수 ai, bi (1 ≤ ai, bi ≤ 250)가 주어진다. 

여기서 ai와 bi는 각각 작업 를 머신 A와 B에서 완료하는데 걸리는 시간이다.​ 

출력은 표준출력을 사용한다. 모든 작업 t1, t2, … , tn을 완료하기 위한 최소의 완료시간을 한 줄에 출력한다.