Để kết thúc buổi sinh hoạt lớp ~9A~ vui vẻ, cô chủ nhiệm đã chuẩn bị ~N~ (~N ≤ 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ổ ~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 vào

• Dòng đầu tiên chứa số nguyên ~N~ (~N ≤ 500000~, ~N~ là một số chẵn).
• ~N~ dòng tiếp theo, mỗi dòng chứa hai giá trị yêu thích của mỗi tổ (là một số nguyên dương nhỏ hơn hoặc bằng ~100~).

Dữ liệu ra

• Một dòng duy nhất chứa tổng giá trị ưa thích lớn nhất của hai tổ.

Ví dụ

Dữ liệu vào

4
1 2
2 3
3 5
2 1

Dữ liệu ra

11