Problems
Морская прогулка
Морская прогулка
Есть несколько катеров и большая группа людей. Для каждого катера известны его вместимость и цена на билет. Для каждого человека известно, на каких катерах он предпочел бы прокатиться. Требуется распределить людей по катерам на одну морскую прогулку так, чтобы суммарная стоимость, потраченная на билеты, была минимальна.
\InputFile
Два числа \textbf{N} и \textbf{K} (\textbf{1} ≤ \textbf{N} ≤ \textbf{16}, \textbf{1} ≤ \textbf{K} ≤ \textbf{100}) - количество катеров и людей. \textbf{N} строк по два числа в каждой - \textbf{s}, \textbf{c}(\textbf{0 }≤ \textbf{s} ≤ \textbf{100}, \textbf{0} ≤ \textbf{c} ≤ \textbf{10^6}) - количество мест в катере и стоимость одного билета. Далее \textbf{K} строк, в каждой из которых дано число \textbf{t} - количество катеров, которые подходят текущему человеку, после чего следует список номеров этих катеров. Все номера в пределах от \textbf{1} до \textbf{N}, каждый номер встречается не более одного раза.
\OutputFile
Одно число - суммарная стоимость одной прогулки, либо \textbf{-1}, если всех людей рассадить по катерам не получится.
Input example #1
3 5 1 1 2 2 3 3 3 1 2 3 2 1 2 1 1 2 1 2 3 1 2 3
Output example #1
11