Problem F. Fast battlepass ≡

Statement

Paulundra is playing a multiplayer shooter called Counter-rant. Recently Counter-rant launched a new season of the Battle Pass where you can get n of the m available weapon skins. The skin opening system is unusual: the player is given n runes, to use the rune, you need to insert two crystals of fixed colors into it, after which if the rune fits the weapon, the weapon opens. A rune matches a weapon if the weapon contains both colors contained in the rune. Each weapon skin contains exactly C colors.

The Battle Pass consists of k levels. For each level of the Battle Pass, exactly one crystal is given, for each level the reward is known in advance. For reaching level i, the reward will be a crystal with the color a_i. The player uses the crystals at his own discretion: inserts into any of the runes or does not use the crystal at all. Since it's hard to earn levels, Paulundra wants to know what is the minimum number of Battle Pass levels she needs to unlock in order to get at least p skins, assuming she distributes crystals and runes optimally.

Input format

The first line of the input contains five numbers m, C, n, p and k. This is followed by m lines containing C numbers c_ij each describing the colors of weapon skins with number i. The next n lines contain two numbers each a_i1 and a_i2  — rune descriptions. The last line of the input contains k number S_i, where S_i is the color of the crystal for getting level i

Output format

Print a single integer  — the minimum number of levels you need to get to open at least p skins. If p skins cannot be opened print -1.

Constraints

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

Sample tests

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