36진법

• 모든 숫자들을 10진수로 변환한다. 그 과정에서 36개의 digit들에 대해서, 각각을 Z로 바꿨을때 전체 합이 얼마나 증가하는지를 추가로 계산한다.
• 숫자들의 합을 구하고, 구해놓은 증가량중 가장 큰 K개를 추가로 더해준다.
• 마지막 단계에서 10진수를 36진법으로 변환할 때, 0도 정확히 '0' 으로 변환될 수 있도록 주의할 것.
• 시간복잡도는 10진수 변환과 증가량 계산에 O(N*M) (M=수의 최대 자릿수), 증가량중 가장 큰 K개를 구하기 위해서 정렬하는 데에 O(ClogC + K) (C=36). 상수인 C는 무시하면, O(NM)

"""Solution code for "BOJ 1036. 36진법".

- Problem link: https://www.acmicpc.net/problem/1036
- Solution link: http://www.teferi.net/ps/problems/boj/1036
"""

DIGITS = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'


def to_base36(num):
    if num == 0:
        return '0'
    ret = []
    while num:
        num, r = divmod(num, 36)
        ret.append(DIGITS[r])
    return ''.join(reversed(ret))


def main():
    N = int(input())
    nums = [input() for x in range(N)]
    K = int(input())

    dec = {x: i for i, x in enumerate(DIGITS)}    
    increase = [0] * 36
    dec_sum = 0
    for num in nums:
        r = 1
        num_in_dec = 0
        for ch in reversed(num):
            ch_in_dec = dec[ch]
            num_in_dec += ch_in_dec * r
            increase[ch_in_dec] += (35 - ch_in_dec) * r
            r *= 36
        dec_sum += num_in_dec
    total_increase = sum(sorted(increase, reverse=True)[:K])
    answer = to_base36(dec_sum + total_increase)
    
    print(answer)
    

if __name__ == '__main__':
    main()