Đôi bạn thân Banana và Vulner vừa học về các kiến thức thuật toán thú vị. Banana thì học về đồ thị hai phía, còn Vulner thì học về thành phần liên thông. Trong buổi học nhóm, hai bạn muốn vẽ một đồ thị G hai phía để cho Vulner áp dụng được các kiến thức của mình vào. Banana cho một danh sách tên người, mỗi tên độ dài từ ~2~ đến ~100~, và mỗi người sẽ thích hai con số là độ dài tên của họ ~+1~ với ~-1.~

Ví dụ: Banana sẽ thích số ~5~ và số ~7.~

Khảo sát tên thành viên của CLB H3.2, Banana vẽ ra được một đồ thị hai phía, một bên có các đỉnh ứng với tên người, một bên có các đỉnh ứng với các con số và ai thích số nào thì sẽ có cạnh nối từ tên người đó qua số tương ứng. Bây giờ Vulner muốn tìm thành phần liên thông có số đỉnh lớn nhất của ~G~ (nhắc lại: hai đỉnh thuộc cùng một thành phần liên thông nếu có đường đi từ đỉnh này đến đỉnh kia). Rất đơn giản, bạn áp dụng thuật toán tìm kiếm theo chiều sâu DFS như Sách giáo khoa. Tuy nhiên, danh sách thành viên trong CLB H3.2 không ngắn gọn như Vulner tưởng, mỗi tên người có thể xuất hiện nhiều lần và được cho bởi một danh sách gồm tên + số lần xuất hiện tương ứng. Bạn hãy giúp Vulner trả lời câu hỏi này nhé, bạn ấy rất dễ bị tổn thương nếu bí bài đấy.

Input

Dòng đầu tiên là số ~n~ cho biết danh sách các tên và số lần xuất hiện, trong đó ~1 \le n \le 2023.~ Mỗi dòng tiếp theo trong ~n~ dòng có dạng

~s~ ~m~

trong đó ~s~ là tên, gồm chữ cái đầu viết hoa, các chữ cái sau viết thường, độ dài không quá ~100~, còn ~m~ là số lần mà tên đó xuất hiện, với ~1 \le m \le 10^6.~

Output

Kích thước của thành phần liên thông lớn nhất.

Sample input 1

4
Phu 3
Trung 2
Tai 4
Loc 1

Sample output 1

13

Sample input 2

2
Coconmeongoibencuaso 1
Toithayhoavangtrencoxanh 1

Sample output 2

3

Giải thích: trong VD1, ta thấy đồ thị có ~3+2+4+1=10~ đỉnh bên phía trái ứng với các tên xuất hiện nhiền lần và ~3~ đỉnh bên phải gồm ~2,4,6~ là các con số mà họ thích (Phú, Tài, Lộc cùng thích số ~2,4~, còn Trung thích số ~4,6~). Rõ ràng các bạn trong danh sách đều cùng thích số ~4~ nên tất cả các đỉnh đều cùng một thành phần liên thông kích thước ~10+3=13~; trong VD2, ta thấy hai người này thuộc các TPLT khác nhau (người đầu thích số ~19~ và ~21~ còn người sau thích số ~23~ và ~25~), mỗi người thích hai con số nên có hai TPLT cùng kích thước ~1+2=3.~