Công ty của bạn có \(N\) nhân viên, được gọi lần lượt là Nhân viên \(1\) đến \(N\). Bạn đã nhận được hai đơn đặt hàng công việc, được gọi là Công việc \(A\) và \(B\), cần phải hoàn thành. Nhân viên \(i\) có thể hoàn thành Công việc \(A\) trong \(A_i\) phút và Công việc \(B\) trong \(B_i\) phút.

Bạn sẽ giao mỗi công việc cho một nhân viên. Bạn có thể giao cả hai công việc cho cùng một nhân viên, trong trường hợp đó thời gian mà anh/cô ấy hoàn thành chúng là tổng thời gian mà anh/cô ấy làm riêng lẻ mỗi công việc. Nếu bạn giao công việc cho các nhân viên khác nhau, thời gian để họ hoàn thành là lâu hơn trong số thời gian mà họ làm công việc tương ứng của mình.

Tìm thời gian ngắn nhất cần thiết để hoàn thành các công việc.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên dương \(N\) \((2 \leq N \leq 1000)\).

\(N\) dòng tiếp theo mỗi dòng chứa một cặp số là \(A_i\) và \(B_i\) \((1 \leq A_i, B_i \leq 10^5)\).

OUTPUT FORMAT

In thời gian ngắn nhất có thể cần thiết để hoàn thành công việc, tính bằng phút.

Ví dụ:

Input

3
8 5
4 4
7 9

Output

5

Nếu bạn giao Công việc \(A\) cho Nhân viên \(2\) và Công việc \(B\) cho Nhân viên \(1\), họ sẽ hoàn thành chúng lần lượt trong \(4\) và \(5\) phút. Vì bạn đã giao công việc cho các nhân viên khác nhau, sẽ mất \(max(4,5)=5\) phút để hoàn thành cả hai công việc. Không thể hoàn thành chúng sớm hơn.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House