2026을 2026번 더하면 무엇일까?

이 질문에 암산으로 답하기는 쉽지 않지만, 동물원에서 놀고 있던 판다 한 마리가 그새 $40A0630$이라는 답을 내놓았다. 우리의 영리한 동물 친구에게 박수를 보내 주자.

이상한 점을 눈치챘는가? 당신이 정확히 계산을 마쳤다면 $4104676$이라는 답이 나왔을 것이다. 게다가 판다의 답에는 알파벳도 포함되어 있다!

하지만 판다가 실수한 것은 아닌데, 판다는 손가락이 $12$개라서 $12$진법을 사용하기 때문이다. 즉, 판다는 $2026$을 $12$진법의 수로 해석하여 계산했고, 답으로 내놓은 $40A0630$ 역시 $12$진법의 수이다. 실제로 $2026_{(12)} = 3486_{(10)}$이므로, 판다가 계산한 값은 $2026_{(12)}^2 = 40A0630_{(12)} = 12152196_{(10)}$이다. 이처럼 다른 진법을 사용하면 같은 수나 식에서도 전혀 다른 값이 나오게 된다.

청린은 동물원에 사는 $N$마리 동물들이 사용하는 진법을 조사하여 기록해 두었다. 조사 결과, 각 동물은 $2$진법 이상 $16$진법 이하의 진법 중 하나를 사용하고 있었다.

또한 청린은 벽에 동물들이 적어 둔 것으로 보이는 $N$개의 수를 발견했다. 청린은 수의 개수가 동물원에 사는 동물의 수와 같다는 점에서, 각 동물이 정확히 하나의 수를 적었을 것이라고 추측했다.

물론 청린의 추측이 틀렸을 수도 있다. 예를 들어, 벽에 $20$과 $26$이 적혀 있고 동물원에 $2$진법을 사용하는 동물 한 마리와 $3$진법을 사용하는 동물 한 마리가 있다면, 어떤 식으로 대응시켜도 청린의 추측은 성립하지 않는다. 특히 $26$은 동물원의 어떤 동물이 적었다고 보더라도 올바르지 않다. 모든 동물은 자신이 사용하는 진법으로만 수를 적는다.

청린은 자신의 추측이 성립한다고 가정할 때, 벽에 적힌 수들의 값의 합이 최대가 되는 경우가 궁금해졌다. 하지만 청린은 동물들과 놀아주느라 바빠서 계산할 시간이 없다. 그러니 여러분이 청린을 도와 최댓값을 구해주자!

첫 번째 줄에 동물의 수 $N$이 주어진다. $(1 \leq N \leq 100\,000)$

두 번째 줄에 각 동물이 사용하는 진법이 공백으로 구분되어 $N$개 주어진다. 각 진법은 $2$ 이상 $16$ 이하의 정수이다.

세 번째 줄에 벽에 적힌 수를 나타내는 문자열이 공백으로 구분되어 $N$개 주어진다.

각 문자열의 길이는 $1$ 이상 $10$ 이하이며, $0$부터 $9$, $A$부터 $F$까지의 문자로만 구성된다. 모든 문자열은 $0$으로 시작하지 않는다.

청린의 추측이 성립하는 경우가 존재한다면, 첫 번째 줄에 벽에 적힌 수들을 그 수를 적은 동물의 진법으로 해석한 값의 합이 최대인 경우의 값을 $10$진법으로 출력한다.

그러한 경우가 존재하지 않는다면 대신 $-1$을 출력한다.