1324번 - 젠장 분류

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

어떻게 줍냐면, 무게가 증가되는 순서대로 줍는다. 그런데 문제는 가방이 고물이라 한번 물건을 넣으면 그 크기에 맞게 가방이 변형되어 버린다는 것이다. 그러면 당신은 그 가방에는 딱 크기가 맞는 쓰레기만 넣을 수 있다.

요컨데, 첫날 줍는 쓰레기랑 둘째 날 줍는 쓰레기가 같아야 한다는 것이다.

당신은 최대한 많이 쓰레기를 모으고 싶다. 그런데 당신이 첫째 날 어떤 가방에 아무 쓰레기도 담지 않았다면 옆집 거지 친구 오민식이 그 가방을 빼앗아간다.

당신은 특유의 예지력으로 오늘과 내일, 길거리에 쓰레기가 어떤 식으로 놓여있을지 안다.

당신은 하루마다 최대 몇 개의 쓰레기를 주울 수 있는가?

첫 번째 줄에는 쓰레기의 개수 N이 주어진다. (N ≤ 1,000) 두 번째 줄에는 첫날 쓰레기의 양이 위치 순서대로 각각 N개 주어진다. 세 번째 줄에는 둘째 날 쓰레기의 양이 위치 순서대로 주어진다. 당신은 아침마다 1번 쓰레기가 있는 위치에서 출발하며, 쓰레기를 줍고 나면 뒤로 돌아가서 쓰레기를 주울 수 없다. 쓰레기의 양은 50,000보다 작거나 같은 자연수이다.

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