휴고

시간 제한2초메모리 제한128 MB

요약
중앙 칸에서 시작해 매초 한 칸씩 이동 가능한 캐릭터가 각 나무에서 정해진 시간에 떨어지는 사과를 최대 몇 개 받을 수 있는지 구하는 문제입니다.
난이도

보통10점 중 6점

유형
동적 계획법, 그리디, 시뮬레이션
정답자
아직 제출이 없습니다

문제

휴고는 화면 아래쪽의 길을 따라 움직이며 나무에서 떨어지는 사과를 최대한 많이 잡아야 하는 게임 캐릭터이다. 길은 같은 크기의 N칸으로 나뉘어 있고, 왼쪽 끝 칸부터 오른쪽 끝 칸까지 차례로 1번부터 N번까지 번호가 붙어 있다. 각 칸 위에는 사과나무가 하나씩 있다. 시간이 지날 때마다 어떤 나무에서 사과 하나가 떨어진다.

게임이 시작될 때 휴고는 가운데 칸에 서 있다. N은 홀수이다. 매초가 끝날 때, 휴고는 현재 칸 P에서 왼쪽의 P-1번 칸으로 이동하거나, 오른쪽의 P+1번 칸으로 이동하거나, 그대로 있을 수 있다. 따라서 시간 1에는 아직 시작 칸에 있다. 사과가 떨어지는 시각에 휴고가 그 나무 아래 칸에 있으면 그 사과를 잡는다. 휴고는 모든 사과가 언제 어느 나무에서 떨어지는지 미리 알고 있다.

휴고가 잡을 수 있는 사과의 최대 개수를 구하라.

입력

첫째 줄에 칸의 수를 나타내는 홀수 정수 N이 주어진다. 1 <= N <= 999이다.

다음 N개의 줄에는 떨어지는 사과 정보가 주어진다. M번째 나무의 정보는 M+1번째 줄에 주어진다. 각 줄은 정수 K로 시작하며, 이어서 사과가 떨어지는 시각을 나타내는 K개의 정수가 오름차순으로 주어진다. 1 <= K <= 3000이고, 가장 큰 시각은 100000 이하이다.

출력

휴고가 잡을 수 있는 사과의 최대 개수를 첫째 줄에 출력한다.

예제3

  1. 예제 1

    입력
    5
2 2 6
2 1 5
1 4
1 3
1 2
    예상 출력
    4

  2. 예제 2

    입력
    7
2 1 2
1 8
2 2 3
2 2 5
2 1 2
2 3 5
2 3 7
    예상 출력
    4

  3. 예제 3

    입력
    7
2 6 7
3 5 7 8
2 2 4
3 2 3 5
3 5 6 7
2 3 6
1 5
    예상 출력
    7