시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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