반란

예레나 안드레예브나는 포마의 말썽에 지쳐 그에게 제대로 된 벌을 주기로 했다. 그런데 말없는 조수가 공장 노동자들이 반란을 일으켰다는 내용의 쪽지를 건넸다. 예레나 안드레예브나는 계획을 접고 포마에게 무슨 일이 일어나고 있는지 알아보라고 맡겼다.

공장에 도착한 포마는 $n$개의 조가 있다는 것을 알았다. 조 $i$에는 $k_i$명의 노동자가 있었고, 모두 무언가에 불만이 있었다. 사태를 가라앉히기 위해 포마는 각 조마다 우두머리를 뽑기로 했다. 우두머리는 노동자 중에서 골라야 한다. 모든 노동자의 소속 조와 임금은 알려져 있다. 포마는 각 조에서 노동자를 정확히 한 명씩 골라 어느 조든 한 조의 우두머리로 세우려 한다. 각 조에는 우두머리가 정확히 한 명 있어야 한다. 포마는 또한 우두머리를 제외하고 조에 남은 노동자들의 임금 합이 그 조 우두머리의 임금보다 크지 않기를 바란다. 여기에 바람이 하나 더 있다. 예레나 안드레예브나를 기쁘게 하려고, 우두머리들의 임금 합이 최소가 되도록 배치하고 싶어 한다.

프시흐는 지금 바빠서, 포마는 너에게 도움을 청했다. 다들 알다시피 그의 부탁은 거절하지 않는 편이 좋다.

첫 줄에 두 정수 $n$과 $k$가 주어진다 ($1 \le n \le 15$, $n \le k \le 50$). $n$은 조의 수이고, $k$는 모든 조의 노동자 수를 합한 값이다. 이어지는 각 줄은 정수 $s$ ($1 \le s \le k$)로 시작한다. 이는 해당 조의 노동자 수이다. 그 뒤에 정수 $s$개가 $a_i$ ($1 \le a_i \le 10^7$)로 주어지며, 각각 그 조 노동자의 임금이다.

답을 한 줄에 출력한다. 답이 존재하지 않으면 $-1$을 출력한다.