Để kết thúc buổi sinh hoạt lớp 9A vui vẻ, cô chủ nhiệm đã chuẩn bị ~N~ (~N \le 500000~, ~N~ là một số chẵn) phần quà cho hai tổ. Mỗi tổ sẽ dán một giá trị ưa thích (là một số nguyên dương nhỏ hơn hoặc bằng ~100~) mà mình nghĩ vào phần quà. Sau đó, cô chủ nhiệm chia cho mỗi tổ ~\frac{N}{2}~ phần quà sao cho tổng giá trị ưa thích của hai tổ là lớn nhất.

Yêu cầu

Bạn hãy giúp cô chủ nhiệm tìm tổng giá trị ưa thích lớn nhất của hai tổ theo cách chia quà trên.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên gồm số ~N~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ gồm hai giá trị ưa thích của mỗi tổ ~(1 \le i \le N)~.

Dữ liệu đầu ra

Gồm một dòng duy nhất là kết quả của bài.

Ví dụ

Ví dụ 1

INPUT

4
1 2
2 3
3 5
2 1

OUTPUT

11