1324번 - 젠장

당신은 게임을 하다 걸려서 사회봉사를 해야 한다. 당신은 2일 동안 길 하나의 쓰레기를 주우려 한다. “이런 젠장”

매일 아침 첫 번째 쓰레기가 있는 위치에서 출발하여 N번째 쓰레기가 있는 위치까지 걸어가면서, 길에 놓여있는 쓰레기를 쓰레기 봉투에 담아야 한다. 모든 쓰레기를 주울 필요는 없으나, 걸어간 길을 되돌아갈 수는 없기 때문에 쓰레기는 항상 위치 순으로 주워야 한다.

그런데 쓰레기 봉투가 고물이라서 다음과 같은 제약이 있다.

• 첫째 날과 둘째 날 각각에 주운 쓰레기의 크기가 단조 증가해야 한다. 다시 말하면, 두 번째 또는 그 이후로 주운 쓰레기의 크기는 바로 전에 주운 쓰레기의 크기보다 크거나 같아야 한다.
• 각 날에 주운 쓰레기들의 개수와 크기는 완전히 같아야 한다.

예를 들어, 첫째 날에는 크기가 2, 3, 3, 4인 쓰레기를 차례로 주울 수 있지만, 크기가 4, 2, 3, 3인 쓰레기를 차례로 주울 수는 없다. 또한 첫째 날에 크기가 2, 3, 3, 4인 쓰레기를 주웠다면, 둘째 날에도 정확히 크기가 2, 3, 3, 4인 쓰레기를 주워야 한다.

당신은 특유의 예지력으로 오늘과 내일 길거리에 쓰레기가 어떤 식으로 놓여있을지 안다. 하루마다 최대 몇 개의 쓰레기를 주울 수 있을까?

첫 번째 줄에는 쓰레기의 개수 N이 주어진다. (N ≤ 1,000) 두 번째 줄에는 첫째 날 쓰레기의 크기가 위치 순서대로 각각 N개 주어진다. 세 번째 줄에는 둘째 날 쓰레기의 크기가 위치 순서대로 주어진다. 쓰레기의 크기는 50,000보다 작거나 같은 자연수이다.

하루마다 주울 수 있는 쓰레기의 최대 개수를 출력한다.