Зоряне ім'я

Обмеження: 2 сек., 256 МіБ

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

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Обмеження

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

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

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

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

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 5 10 a 3 b 4 c 18 aba aab caba bb a	aab