Base-36 Number

Time limit2sMemory limit128 MB

Summary

Pick K base-36 digit symbols to replace with Z across N numbers so their sum is maximized, then output that sum in base 36.

Level: Medium5 of 10
Topics: Greedy, Math, Sorting, String
Solved: No attempts yet

Problem

A base-36 digit is one of the digits from 0 to 9 or one of the uppercase letters from A to Z. The letters A through Z represent the values 10 through 35, respectively.

You are given N base-36 numbers. Choose K digit symbols among the 36 possible symbols, then replace every occurrence of each chosen symbol in all N numbers with Z. After the replacements, add all N numbers.

Write a program that finds the largest possible sum. Print that maximum sum in base 36.

Input

The first line contains the number of values N. Each of the next N lines contains one base-36 number. N is at most 50, and each number has length at most 50. The last line contains K. K is either 0 or a positive integer not greater than 36.

Output

Print the answer on one line.

Examples5

Example 1
Input
```
5
GOOD
LUCK
AND
HAVE
FUN
7
```
Expected output
```
31YUB
```
Example 2
Input
```
1
HELLO
2
```
Expected output
```
ZZLLO
```

Example 3

Input

5
500
POINTS
FOR
THIS
PROBLEM
5

Expected output

1100TC85

Example 4
Input
```
6
TO
BE
OR
NOT
TO
BE
0
```
Expected output
```
QNO
```
Example 5
Input
```
1
KEQUALS36
36
```
Expected output
```
ZZZZZZZZZ
```