Факултетот ФИНКИ настана како спој на вработените од двата постојни институти за информатика при УКИМ. Предавачите од двата института сега ќе бидат предавачи на ФИНКИ. Но, во програмата на ФИНКИ има и нови предмети за кои можеби се уште нема предавачи. Дополнително, за да осигури беспрекорно одвивање на наставата, деканот сака, за секој предмет, да има по најмалку двајца предавачи.

Распишан е огласот за нови вработувања и на истиот се пријавиле K апликанти. За сите нив се знае платата која ја побаруваат и кои предмети може да ги предаваат. Ако дополнително имате информација за бројот на предмети и информација за постојните предавачи (плата, и листа на предмети кои тие може да ги предаваат) одредете колку најмалку пари ќе треба да исплаќа ФИНКИ за плата секој месец.

Забелешка: Постојните предавачи остануваат вработени, а се вработуваат и дел од апликантите со цел да се задоволи барањето на деканот (да има најмалку по двајца предавачи за секој предмет).

Влез

Во првиот ред се запишани два цели броја: N - кој го означува бројот на предмети, и M (1 <= N, M <= 8) – кој го означува бројот на моментно вработени предавачи. Во следните М редови се дадени информации за секој од моментно вработените предавачи (во формат "Pi Ti Si₁ Si₂ ... Si_Ti", каде Pi (8000 <= Pi <= 80000), ја означува платата која ја бара i-тиот предавач, Ti (1 <= Ti <= N) го означува бројот на предмети кои тој може да ги предава, и Si₁, Si₂, ..., Si_Ti (1 <= Si₁, Si₂, ..., Si_Ti <= N) ги означуваат предметите кои i-тиот предавач може да ги предава.

Во следниот ред е даден еден цел број K (1 <= K <= 200), кој го означува бројот на апликанти. Во наредните K редови се дадени информации за апликантите (во ист формат како и за моментно вработени предавачи).

Излез

На стандарден излез отпечатете колку најмалку пари ќе треба да исплаќа ФИНКИ за плата секој месец, a притоа да се задоволи барањето на деканот (да има по најмалку двајца предавачи за секој предмет). Секогаш ќе постои решение.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
2 2
15000 1 2
55000 1 1
2
23000 2 1 2
22000 2 1 2

излез
92000

влез
2 1
15000 1 1
2
22000 2 1 2
23000 2 1 2

излез
60000