Processing math: 100%

Problem F. Fast battlepass

Author:И. Блинов   Time limit:2 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

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 ai. 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 cij each describing the colors of weapon skins with number i. The next n lines contain two numbers each ai1 and ai2  — rune descriptions. The last line of the input contains k number Si, where Si 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

1m100

2C10

1n,p10

1k106

1ai1,ai2,Si,cij109

ai1ai2

Sample tests

No. Standard input Standard output
1
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
2
1 2 1 1 1
100 100000
1 2
1
-1
3
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

0.068s 0.012s 13