복권 재미 타임

복권의 가장 큰 재미는 보통 아주 적은 당첨금을 받는 데 있지 않고, 거의 불가능하지만 받을 수도 있는 큰 행운을 꿈꾸는 데 있다.

가진 복권이 여러 장 있고, 각 복권에는 6자리 숫자가 적혀 있다. 모든 숫자는 서로 다르다. 내일이 추첨일이며, 상금은 다음과 같다.

• 1등 30만 엔은 복권의 6자리가 1등 당첨번호 6자리와 모두 일치하는 복권이 받는다.
• 2등 4천 엔은 복권의 끝 4자리가 2등 당첨번호 4자리와 일치하는 복권이 모두 받는다.
• 3등 500엔은 복권의 끝 2자리가 3개의 3등 당첨번호 중 하나와 일치하는 복권이 모두 받는다.

복권의 6자리와 모든 당첨번호는 0으로 시작할 수 있다.

모든 당첨번호의 끝 두 자리는 서로 다르게 정해진다. 3등에 당첨된 복권이 1등이나 2등에도 동시에 당첨되지 않게 하기 위해서다. 이 규칙 때문에 1등과 2등 당첨번호의 끝 두 자리도 서로 다르다.

복권 추첨의 절정을 즐기기 위해, 가진 복권으로 받을 수 있는 최대 금액을 계산하려고 한다. 복권이 너무 많아 손으로 계산하기 어려우니, 이를 계산하는 프로그램을 작성하는 것도 즐거운 일이다.

첫 줄에 양의 정수 $n$ ($n \le 10^5$)이 주어진다. 이는 가진 복권의 개수이다. 다음 $n$개 줄에는 각 복권의 6자리 숫자가 한 줄에 하나씩 주어진다. $n$개의 숫자는 모두 서로 다르다.

가진 복권으로 얻을 수 있는 당첨 상금 합계의 최댓값을 한 줄에 출력한다.

첫 번째 예제에서는 다음 당첨 조합이 합계 309500엔의 최댓값을 만든다.

• 1등 당첨번호 382947의 복권 한 장이 30만 엔을 받는다.
• 2등 당첨번호 4837로 924837과 294837 두 장이 각각 4천 엔을 받는다.
• 3등 당첨번호 07과 45로 034207, 083907, 372745 세 장이 각각 500엔을 받는다. 2등 당첨번호 4837의 끝 두 자리가 37이므로 37은 3등 당첨번호가 될 수 없다. 따라서 274637 복권은 아무것도 받지 못한다. 남은 3등 당첨번호가 무엇이든 더 당첨될 복권은 없다.

두 번째 예제에서는 10장 중 9장의 끝 두 자리가 89로 같다. 3등 당첨번호 89는 이 9장에 500엔씩 주어 합계 4500엔을 만든다. 이는 이 9장 중 한 장이 받을 수 있는 2등 4천 엔보다 많다. 남은 복권 263784는 1등 상금을 받는다.