Problem D
Baba Yaga

On his usual shopping trip to buy stellar glyphs Atli noticed that Baba Yaga had expanded her list of wares and had started selling various potions. When asked why she didn’t usually stock those she muttered something about them being too strong for travellers. When Atli takes a better look he sees that the potions have varying prices and different effects. Baba Yaga warns him though that this kind of magic is fickle. If he were to ingest two potions that have a common effect, that effect would cancel out and he’d have to find a third potion to reactivate it. Atli of course wants to be as prepared for what is to come as possible, so he wonders if he can buy some set of potions which will leave him with every single possible effect active. Furthermore he’d of course like to do so in the cheapest manner possible.

Input

The first line of the input contains two integers $1 \leq n \leq 10^3$ and $1 \leq b \leq 16$ where $n$ is the number of different potions and $b$ is the number of possible effects they can have. Then follow $n$ descriptions of potions, each two lines in length. The first line contains two integers $0 \leq c \leq 10^9$ and $1 \leq k \leq b$, the cost of the potion and the number of effects it has. The second line contains $k$ integers $1 \leq b_ i \leq b$, the indices of the effects the potion has.

Output

If there is no way to obtain a set of potions activating all effects, print ‘Ekki haegt!’. Otherwise print the minimal cost of obtaining such a set of potions.

6 5
10 2
1 3
4 2
1 2
4 2
2 3
10 2
2 5
2 2
4 5
4 1
5

24

3 3
10 2
1 2
10 2
1 3
10 2
2 3

Ekki haegt!

1 3
10 2
1 2

Ekki haegt!