Зоряне ім'я

Limits: 2 sec., 256 MiB

Недарма кажуть: «Як корабель назвеш, так він і попливе». Скоро мають відбутися гонки на подах, і Енекін думає, як назвати його под, та гордо написати це ім’я на корпусі.

У місцевому алфавіті є \(m\) букв, які ми змоделюємо як малі букви латинського алфавіту (a-z). Різні букви мають різну площу, а тому вартість їхнього написання різна. Енекін витратив майже всі гроші на деталі, тому бюджет на фарбу обмежений (\(k\) монет). Проте він уже придумав цілих \(n\) варіантів для назви!

Вам потрібно обрати найдорожчий варіант назви, який усе ще по кишені Енекіну. Якщо таких варіантів декілька, оберіть лексикографічно найменший (тобто той, який би був у словнику першим).

Input

Перший рядок містить три цілих числа \(m\), \(n\), \(k\) — кількість букв в алфавіті, кількість варіантів назви та залишок коштів в Енекіна.

Кожен із наступних \(m\) рядків містить один символ латинського алфавіту та вартість його написання. Жоден символ не трапиться двічі.

У наступних \(n\) рядках містяться варіанти назв по одному варіанту в рядку.

Output

У єдиному рядку виведіть назву.

Constraints

\(1 \le m \le 26\),

\(1 \le n \le 10^3\),

\(1 \le k \le 10^6\),

кожна назва матиме не більше ніж 10 символів,

вартість кожного символа — натуральне число до \(10^3\),

гарантується, що бюджетна назва завжди існує.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 5 10 a 3 b 4 c 18 aba aab caba bb a	aab