시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 24 8 6 37.500%

문제

영선이는 오늘도 일을 한다. 그리고 내일도… 모레도…

어느 날 영선이에게 할당된 업무들이 주어졌다. 이 업무들은 특정 기간에만 일을 할 수 있는데, 영선이는 특이하게 업무를 시작하는 날에 따라서 일하는 기간이 달라진다.

예를 들어, [1,5]에만 할 수 있는 업무가 있는데 1일에 시작하면 4일, 2일에 시작하면 2일,3일에 시작하면 3일,4일에 시작하면 5일, 5일에 시작하면 2일이라고 할 때, 4일,5일에 시작했다가는 기간안에 끝낼 수 없고, 2일에 시작하면 3일까지 일을 해서 가장 빨리 끝낼 수 있다.

또한, 업무를 끝낸 날에는 바로 다른 업무를 시작할 수 있다.

다음과 같이 업무들의 정보들이 주어질 때, 가장 많은 업무들을 볼 때 그 업무 수를 출력하시오.

입력

첫째 줄에는 업무의 개수 n개가 주어진다.(1≤n≤15)

다음 n줄에는 a,b가 주어지고, 바로 다음에 b-a+1개의 정수가 주어지는데, 이는 i번째 줄의 업무가 [a,b] 기간동안 할 수 있으며, a…b까지 그 날 시작하면 일하는 시간Ti이 주어진다.(1≤a≤b≤100, 1≤Ti≤100)

출력

최대로 많이 할 수 있는 업무의 수를 출력하시오.

예제 입력 1

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

예제 출력 1

2