Призы Фастфуда
Во время региональных соревнований канадское отделение популярного ресторана быстрого питания обычно проводит игру для продвижения своего бизнеса. Некоторые продукты предоставляют наклейки, и определенные наборы различных наклеек можно обменять на денежные призы. Если приз требует наклейки типов T_1, T_2, ..., T_k, то вы можете получить этот приз, если у вас есть по одной наклейке каждого типа T_1, T_2, ..., T_k. Каждая наклейка может быть использована только для получения одного приза. Однако вы можете получить один и тот же приз несколько раз, если у вас есть несколько наклеек каждого типа. Ни один из призов не требует одинаковых типов наклеек. Могут быть наклейки, которые нельзя использовать для получения денежного приза (например, наклейка на бесплатный молочный коктейль).
Во время вашей поездки на региональные соревнования ваш тренер заставил вас поесть в этом ресторане и собрал все наклейки вместе. Сколько денег может получить ваш тренер?
Входные данные
Входные данные состоят из нескольких тестов. Первая строка содержит одно целое число, не более 1000, указывающее количество тестов. Каждый тест начинается со строки, содержащей два целых числа n (1 ≤ n ≤ 10) и m (1 ≤ m ≤ 30), где n — количество различных типов призов, а m — количество различных типов наклеек (типы обозначены числами 1, 2, ..., m). Следующие n строк описывают призы. Каждая из этих строк начинается с целого числа k (1 ≤ k ≤ m), указывающего количество типов наклеек, необходимых для получения приза. Далее следуют k целых чисел, указывающих типы необходимых наклеек. Последнее целое число в каждой строке — это (положительная) денежная стоимость приза (не более 1000000). Последняя строка каждого теста содержит m неотрицательных целых чисел, где i-е число указывает количество наклеек типа i, собранных вашим тренером. Не более 100 наклеек каждого типа.
Выходные данные
Для каждого теста выведите в одной строке общую стоимость денежных призов, которые можно получить.