시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 4 2 2 50.000%

문제

영선이가 다니는 학교, sys학교는 자연재해를 겪어 일부 교실을 사용할 수 없게 되었다. 다행히 현재 m개의 교실은 사용이 가능하다. 현재 sys학교에는 n학년이 존재하며, 각 학년별로 a반이 존재한다. 교실이 부족하여 해당 학년의 모든 반의 학생들을 한 교실에 몰아넣을 것이다. 그래도 부족하면, 그나마 교육수준이 비슷한 인접한 두 학년의 모든 반을 한 교실에 넣을 것이다. 예를 들면 2학년은 1학년이나 3학년이 그나마 교육수준이 비슷하므로 둘 중 하나와 같은 교실을 사용하게 할 수 있다.

하지만, 같은 학년이면 공통으로 듣는 과목이 있지만, 다른 학년끼리는 한 학년 차이라고 하더라도 문이과차이, 세부 선택과목 차이 등으로 다른 학년끼리는 도저히 같이 들을 수 없는 반들이 있다.

또한, 교실의 수가 모질라는 형편이기에, 형평성 문제로, 두 학년이 한 교실을 쓰는 경우는 있어도, 한 학년이 두 교실을 쓰는 경우는 없다. 즉, 두 학년사이에서 도저히 같이 들을 수 없는 반들 끼리는 한쪽 반이 버려진다. 하지만 상황에 따라 한 학년이 교실을 하나도 쓰지 못하는 경우도 있다.

다음과 같은 상황이 주어질 때, m개의 교실의 n학년을 배정할 때, 최대로 많은 반들이 교실을 배정받게 하고 싶다. 이때, 최대가 되는 반의 개수를 출력하시오.

입력

첫째 줄에는 학교의 학년 수 n, 사용할 수 있는 교실의 수 m이 주어진다.(1≤n≤50,floor(n/2)≤m≤n)

다음 줄에는 각 학년별로 반의 수a가 주어지고, 다음 a줄에는 상위 학년과 같이 들을 수 없는 반들의 개수 b, 같이 들을 수 없는 반의 숫자가 b개 주어진다.(1≤a(i)≤100,0≤b≤a(i+1))

최고학년의 입력은 반의 수 a 만 들어온다.

출력

m개의 교실에 적절히 배정했을 때, 모든 학년에 배정된 반들의 수의 최댓값을 출력하시오.

예제 입력 1

4 2
3
1 1
1 1
2 1 2
2
0
1 3
5 
0
3 1 2 3
2 1 3
0
1 2
3

예제 출력 1

9