호화 장비

텔레콤 파리테크의 등산 및 모험 동아리는 백컨트리에서 하이킹, 암벽 등반, 스키를 즐기지 않을 때면 탐험을 뒷받침할 새 장비를 끊임없이 찾아 나선다. 운 좋게도 지난주에 이 동아리는 유명 산악 장비 상점 "인디애나 존스의 동굴"을 운영하는 동문으로부터 후한 기부를 받았다. 그 상점 주인은 동아리에 C 초코코인 상당의 상품권을 주었고, 동아리는 이 상품권을 그녀의 상점에서 사용할 수 있다. 그러나 상품권은 한 번만 사용할 수 있으며, 사용한 뒤 남은 금액은 돌이킬 수 없이 사라진다.

등산 및 모험 동아리는 이미 구매하고 싶은 K가지 장비 종류의 목록을 작성했다. 텐트, 침낭, 버너, 로프, 하네스, 카라비너, 아이스 액스, 크램폰, 아이스 스크루 등이다. 각 장비 종류별로 몇 개를 구매하고 싶은지도 알고 있다. 인디애나 존스의 동굴에는 각 장비 종류마다 여러 모델이 있다. 어떤 모델은 꽤 저렴하고 어떤 모델은 더 비싸다. 모든 모델이 동아리의 안전 기준을 통과하므로 동아리는 어떤 모델이든 구매해도 괜찮다. 따라서 동아리는 각 장비 종류마다 원하는 수량만큼 구매할 모델을 하나 골라야 한다. 정비를 간소화하기 위해 장비 종류마다 모델을 하나만 선택한다. 각 장비 종류마다 모델을 고를 수 있으므로, 동아리의 목표는 잃게 되는 초코코인의 수가 최소가 되도록 돈을 쓰는 것이다.

입력은 여러 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수를 나타내는 정수가 하나 있다. 그다음에 각 테스트 케이스가 이어진다. 테스트 케이스의 첫 줄에는 단일 공백으로 구분된 두 정수 0 ≤ C ≤ 10000과 0 ≤ K ≤ 45가 있다. C는 초코코인 단위의 상품권 금액이고 K는 동아리가 구매하려는 서로 다른 장비 종류의 수이다. 그다음 K개의 줄이 각 장비 종류를 설명하며, 각 줄에는 단일 공백으로 구분된 다음 정수들이 있다. 첫 정수 1 ≤ Mi ≤ 25는 이 장비 종류에 대해 구매할 수 있는 모델의 수이고, 다음 M개의 정수 1 ≤ Pi,j ≤ 5000은 각 모델의 가격이며, 마지막 정수 0 ≤ Qi ≤ 10은 동아리가 이 장비 종류를 몇 개 구매하려는지를 나타낸다.

입력의 각 테스트 케이스마다 프로그램은 한 줄을 출력해야 한다. 각 장비 종류마다 요청한 수량을 구매할 수 있는 모델 선택이 없으면 그 줄에는 IMPOSSIBLE을 출력한다. 그렇지 않으면 그 줄에는, 요청한 수량을 각 장비 종류별로 구매할 때 잃게 되는 초코코인의 수를 최소화하는 모델 선택에서 잃게 되는 초코코인의 수 d ≥ 0을 양의 정수로 출력한다. 출력에 빈 줄이 있어서는 안 된다.