KALLAX 시공

시간 제한1초메모리 제한512 MB

요약

이전 회사의 묶음 크기를 조합해 목표 크기를 만드는 회사 사슬이 주어질 때, B개 이상을 보장하는 가장 작은 광고 묶음 크기를 찾는다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 그리디, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

당신은 IKEA의 사장이고, 볼트 B개를 대량으로 주문해야 한다. 볼트 제조사는 하나뿐이지만, 이 볼트를 묶음(예: 상자, 팔레트)으로 재판매하는 회사는 여러 곳이다. 이 회사들은 방향성 사슬을 이루며, 각 회사는 이전 회사에서 묶음을 사서 새 묶음으로 합친다(물론 새 묶음에는 그 회사의 로고가 멋지게 박혀 있다).

얼핏 보면 이 중간 회사들은 이득이 없어 보인다. 이전 회사의 묶음을 더 큰 묶음으로 다시 포장할 뿐이기 때문이다. 그러나 모든 회사에는 각자의 목표 고객이 있어, 특정 개수의 볼트가 든 묶음을 팔고 싶어 한다. 각 회사는 이전 회사의 묶음만 사용하므로 지정한 개수와 정확히 일치하는 묶음을 만들지 못할 수도 있다. 대신 회사가 X개의 볼트가 반드시 들어 있다고 보장되는 묶음을 만들고 싶다면, 이전 회사의 여러 묶음을 묶어서 그 묶음들에 표시된 볼트 개수의 합이 X 이상이 되게 한다. 이런 조합이 여러 개라면, 표시된 합이 최소인 조합 중 아무거나 하나를 고른다. 더 자세한 이해를 위해 아래 예시를 보라. 각 회사는 이전 회사가 제공하는 묶음 크기 외에는 공급망에 대한 지식이 없다.

당신은 이를 이용할 수 있다는 것을 깨닫는다. 회사가 묶음에 특정 개수의 볼트가 있다고 명시해도, 실제로는 더 많이 들어 있을 수 있다! 따라서 당신은 필요한 볼트 개수 이상을 담으면서 광고된 개수가 가장 낮은 묶음을 찾는 여정을 시작한다. 사업상의 인맥 덕분에, 당신은 제조사를 포함하여 어느 회사에서든 묶음을 살 수 있다.

입력

입력의 첫 줄에는 필요한 볼트 개수를 나타내는 정수 1 ≤ B ≤ 10^3이 주어진다.
입력의 둘째 줄에는 회사의 수를 나타내는 정수 1 ≤ k ≤ 10이 주어진다.
다음 k개의 줄은 각각 회사 하나를 설명한다. 각 줄은 정수 l_i, n_1, n_2, ..., n_{l_i}로 이루어지며, 이는 회사 i가 1 ≤ l_i ≤ 10가지 종류의 묶음을 각각 0 < n_1 < n_2 < ... < n_{l_i} ≤ 10^3 크기로 생산한다는 뜻이다.

출력

회사들이 묶음을 어떻게 만드는지에 관계없이 B개 이상의 볼트가 들어 있는 것을 보장하는, 구매 가능한 묶음의 최소 크기를 나타내는 정수 하나를 출력한다. 이것이 불가능하면 impossible을 출력한다.

예제4

예제 1
입력
```
310
3
2 40 65
2 100 150
2 300 320
```
예상 출력
```
300
```

예제 2

입력

예상 출력

impossible

예제 3
입력
```
90
2
2 20 35
2 88 200
```
예상 출력
```
88
```
예제 4
입력
```
91
2
2 20 35
2 88 200
```
예상 출력
```
200
```