Задача F. Fast battlepass ≡

Условие

Паулундра играет в многопользовательский шутер Counter-rant. Совсем недавно в игре стартовал новый сезон боевого пропуска в котором можно получить n из m доступных скинов для оружия. Система открытия скинов несколько необычная: игроку даётся n рун в каждую руну нужно вставить два кристалла цвета которых фиксированы, после чего если руна подходит к оружию, то оружие открывается. Руна подходит к оружию, если оружие содержит оба цвета содержащиеся в руне. Каждое оружие содержит в себе ровно C цветов.

Боевой пропуск состоит из k уровней. За каждый уровень боевого пропуска даётся ровно одни кристалл, для каждого уровня награда известна заранее. За достижение уровня i наградой будет кристалл с цветом a_i. Игрок использует кристалы и руны по своему усмотрению. Так как зарабатывать уровни довольно тяжело, Паулундра хочет узнать какое минимальное количество уровней боевого пропуска она должна открыть для того чтоб получить хотя бы p скинов, при условии, что она будет оптимально распределять кристалы и руны.

Формат входных данных

Первая строка входных данных содержит пять чисел m, C, n, p и k. Далее следует m строк содержащих по C чисел c_ij описывающих цвета оружия с номером i. Следующие n строк содержат по два числа a_i1 и a_i2  — описания рун. Последняя строка входного содержит k числе S_i, где S_i цвет кристалла за получения уровня i.

Формат выходных данных

Выведите одно целое число  — минимальное количество уровней, которое необходимо получить для открытия хотя бы p скинов. Если p скинов открыть невозможно выведите -1.

Ограничения

1 ≤ m ≤ 100

2 ≤ C ≤ 10

1 ≤ n, p ≤ 10

1 ≤ k ≤ 10⁶

1 ≤ a_i1, a_i2, S_i, c_ij ≤ 10⁹

a_i1 ≠ a_i2

Примеры тестов

5 3 5 4 10
1 2 3
2 3 4
3 4 5
3 4 6
5 6 7
2 3
2 3
3 4
4 5
10 9
4 4 5 2 3 2 3 3 10 10

8

1 2 1 1 1
100 100000
1 2
1

-1

3 2 4 1 5
2 1
3 1
8 8
1 2
1 3
3 4
1 2
1 2 3 1 2

2