책 구매

서로 다른 종류의 책 $N$권(번호는 $1$부터 $N$까지)을 구매하려고 하며, 현재 여러 인터넷 서점의 가격을 확인하고 있다. 각 책은 적어도 한 서점에서 판매되며, 서점마다 가격이 다를 수 있다. 또한 각 서점에서 주문하면 배송비가 부과된다. 배송비는 서점마다 다를 수 있지만, 주문하기로 한 책이 몇 권이든 같은 서점의 배송비는 항상 동일하다. 모든 책을 구매하기 위해 지불해야 하는 최소 금액을 계산한다. 어떤 수의 서점에서든 어떤 수의 책이든 주문할 수 있다.

점수

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$30$| $M=2$

$2$ |$70$| 추가 제한이 없다.

첫째 줄에는 구매할 책의 수를 나타내는 두 정수 $N$ ($1 \le N \le 100$)와 서점의 수를 나타내는 $M$ $(1 \le M \le 15$)가 주어진다.

이후 입력에는 각 서점에 대한 설명이 주어진다. 각 서점은 먼저 그 서점에 있는 책 중 구매하려는 책의 수 $K$와 해당 서점의 배송비를 나타내는 두 정수로 설명된다. 다음 $K$개의 줄에는 각각 그 서점에 있는 책의 번호와 가격을 나타내는 두 정수가 주어진다.

모든 가격과 배송비는 스웨덴 크로나 단위의 정수이며, $10\,000$을 초과하지 않는다. 책 가격은 항상 양수이지만, 일부 서점의 배송비는 무료일 수 있다.

구매하기로 선택한 모든 서점의 배송비를 포함하여 책을 구매하는 데 드는 최소 금액을 출력한다.