Bánh và Kẹo có một bộ cờ domino thiết kế riêng gồm các quân bài được ghi các số từ 0 đến 9. Mỗi quân bài có 2 mặt số trên và dưới. Hình sau là 3 quân bài được sắp sát nhau, khi xếp sát nhau thì các số phía trên của các quân bài tạo thành một con số, tương tự cho dãy dưới, như hình vẽ ta có số 123 dãy trên và 454 cho dãy dưới.

Bánh và Kẹo đưa ra một trò chơi như sau: Mỗi lượt một người chọn ra ~N~ quân cờ, sau đó sắp xếp sát nhau cạnh theo cạnh như hình trên và được hai số, cộng hai số đó lại, ai có điểm cao hơn sẽ thắng. Ví dụ như cách xếp trên của Bánh sẽ thu được tổng là 577.

Viết chương trình giúp Bánh sắp xếp sao cho thu được tổng lớn nhất, giả sử các quân bài có thể quay ngược 180 độ (hoán đổi vị trí hai số trên và dưới).

Input

Dòng đầu tiên chứa số nguyên dương ~N~ thỏa ~1 \le N \le 55~ là số quân bài được chọn.

~N~ dòng tiếp theo, mỗi dòng mô tả một quân bài với hai số nguyên có giá trị từ 0 đến 9.

Output

In ra tổng lớn nhất cần tìm.

Samples

Sample Input

3
1 4
2 5
3 4

Sample Output

775