세계에서 가장 큰 꽃 정원 중 하나를 방문한 후,
리케는 꽃을 매우 좋아하게 되어 아름다운 부케를 만들기 위해 길가에 피어 있는 튤립 몇 송이를 모으기로 결심했다.

그러나 꽃을 모을 때 네덜란드의 엄격한 튤립 보호법에 따라 몇 가지 규칙을 준수해야 한다.

길을 따라 왼쪽에서 오른쪽으로 일렬로 자라는 총 N송이의 튤립이 있으며, 이들은 0번부터 N-1번까지 번호가 매겨져 있다.

튤립 보호법에 따르면, 튤립 i에는 두 개의 정수 l_i와 r_i가 할당된다.

만약 튤립 i가 부케에 포함된다면, 그 튤립의 바로 왼쪽에 있는 l_i송이와 바로 오른쪽에 있는 r_i송이는 부케에 포함될 수 없다.

단, 튤립 i의 왼쪽에 l_i송이보다 적은 튤립이 있거나 오른쪽에 r_i송이보다 적은 튤립이 있는 경우에도 해당 쪽의 모든 튤립이 부케에서 제외된다.

리케는 꽃을 최적으로 선택했을 때 모을 수 있는 튤립의 최대 수가 얼마일지 궁금해한다.

그녀의 질문에 답을 찾아 아름다운 부케를 만들 수 있도록 도와주자!

부케 timer 3s memory 1024MB

부케 3s 1024MB