인하 슈트

규환이는 Iron Man 슈트에서 영감을 받아 Inha 슈트를 만들었다. 이 슈트를 입고 모든 나무의 높이가 20m인 숲을 지나 인하대로 가려고 한다. Inha 슈트는 위아래로만 움직이고, 올라갈 수 있는 높이는 20m까지다. 슈트가 머물 수 있는 높이는 1 이상 20 이하의 정수다.

이동 기능은 다섯 가지다.

• O: 현재 높이에 그대로 머문다.
• A: 위로 1m 올라간다.
• B: 현재 높이만큼 위로 올라간다. 현재 높이가 10m 이상이면 항상 20m로 올라간다.
• C: 아래로 1m 내려간다.
• T: 1 이상 20 이하의 아무 높이로든 순간이동한다.

T 기능은 사용자에게 나쁜 영향을 주므로 사용 횟수가 $K$번으로 제한되고, 되도록 적게 써야 한다.

숲을 지나는 동안 오른쪽에서 강풍이 불어 나무에 부딪힐 위험이 있다. 나무마다 구멍이 뚫려 있어서 구멍이 있는 높이로 지나가면 부딪히지 않는다. 나무와 나무 사이에는 이동 기능을 정확히 한 번 쓸 수 있는 공간이 있다.

규환이는 높이 1m에서 출발하고, 첫 나무를 통과할 때까지도 이동 기능을 한 번만 쓴다. 즉 $i$번째 나무를 지나기 직전에 이동 기능을 한 번 쓰고, 그 결과 높이가 $i$번째 나무의 구멍 높이 중 하나와 같아야 한다. 같지 않으면 나무에 부딪힌다.

예를 들어 T 기능을 최대 2번 쓸 수 있고 나무가 5개이며, 1번부터 5번 나무의 구멍이 각각 한 개씩 높이 1, 2, 4, 6, 5에 있다고 하자.

그림 1. 문제 예시

높이 1에서 O, A, B를 차례로 쓰면 높이가 1, 2, 4로 바뀌어 세 번째 나무까지 통과한다. 높이 4에서 네 번째 나무의 구멍인 높이 6으로 가려면 O는 높이 4, A는 높이 5, B는 높이 8, C는 높이 3이 되므로 이 네 기능으로는 닿지 않는다. T를 한 번 써서 높이 6으로 간 다음 C를 쓰면 높이 5가 되어 마지막 나무까지 통과한다. 그래서 T를 1번만 쓰면 된다.

구멍이 여러 개인 나무에서는 T로 어느 구멍을 고르는지에 따라 이후 경로가 달라지므로 선택이 복잡해진다. 규환이가 T를 가장 적게 쓰고 안전하게 지나가도록 도와주자.

첫 줄에 나무의 개수 $N$ ($1 \le N \le 100$)이 주어진다.

둘째 줄에 T 기능의 제한 횟수 $K$ ($0 \le K \le 50$)가 주어진다.

다음 $N$개의 줄에는 각 줄마다 그 나무의 구멍 개수 $M$ ($1 \le M \le 20$)과 구멍 $M$개의 높이가 공백으로 구분되어 주어진다. 구멍의 높이는 1 이상 20 이하의 정수이고 한 나무 안에서 서로 다르며, 정렬되어 있지 않을 수 있다. 나무는 입력에 주어진 순서대로 지나간다.

마지막 나무까지 안전하게 통과하는 데 필요한 T 기능 사용 횟수의 최솟값을 한 줄에 출력한다. T 기능을 $K$번 이하로 써서 통과할 방법이 없으면 -1을 출력한다.